题目内容

如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是斐波那契式的：
n >= 3
对于所有 i + 2 <= n，都有x[i] + x[i+1]=x[i+2]

给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。
（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例
示例 1：
输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。
示例 2：
输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。
python解法1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def lenLongestFibSubseq(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        S = set(A)
        result = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[i], A[j] 
                length = 2
                while x+y in S:
                    x, y = y, x + y
                    length += 1
                    result = max(result, length)
        return result if result >2 else 0


其中使用了迭代法，主要在于嵌套了三层循环，while的使用很重要。
Java解法1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lenLongestFibSubseq(int[] A) {
        Map map=new HashMap();
        for(int a=0;a < A.length;a++){
             map.put(A[a],a);
        }
        int length=0;
        Map dict=new HashMap();
        for(int k=0;k < A.length;++k){
            for(int j=0;j < k;++j){
                int result=map.getOrDefault(A[k]-A[j],-1);
                if (result=0){
                    int camp=dict.getOrDefault(result*A.length+j,2)+1;
                    dict.put(j*A.length+k,camp);
                    length=Math.max(length,camp);
                }
            }
        }
        return length>2 ? length :0;       
    }
}


使用动态规划，其中getOrDefault函数是可以获取对应键的值，如果值不存在，则提供第二个参数为默认值。可以将该问题抽象出数组索引的最长子序列问题，表达式为len(A[i,j])+1=len(A[j,k]),其中A[i,j]可以表示为i*A.length+j,若使用例如i+j来代替,则有的测试用例无法通过。