如果序列 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] 。
 

提示：

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
（对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

 

思路：

计算到每个位置时   可以得到的最大长度  

用map保存  longest.put(j+"_"+ k, temp);   key：到j为止  并且和k组成数列     value：可以得到的最大长度

详细看代码注释

public int lenLongestFibSubseq(int[] A) {
		int len = A.length;
		Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < len; ++i)
            map.put(A[i], i);  //放入map里面

        int res = 0;
        Map<String, Integer> longest = new HashMap();
        for (int k = 0; k < len; ++k)            //每个位置
            for (int j = 0; j < k; ++j) {        //通过遍历   获取可以组成序列的前一个数字
                int i = map.getOrDefault(A[k] - A[j], -1);      //判断可以组成序列的前两个是否在数组中
                if (i >= 0 && i < j) {           //找到了
                    // 如果找不到到i为止  和j组成序列的长度  则只能i和j配（长度为2）  再和k配
                    int tempLen = longest.getOrDefault(i+"_" + j, 2) + 1;           //1为k本身
                    //到j为止  并且和k组成数列作为key  最大长度作为value
                    longest.put(j+"_"+ k, tempLen);
                    res = Math.max(res, tempLen);
                }
            }

		return res>2?res:0;
	}