解法

set暴力遍历解法

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        Set<Integer> s = new HashSet<>();
        for (int i : arr) {
            s.add(i);
        }
        
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int a = arr[j];
                int b = arr[i] + arr[j];
                int count = 2;
                while (s.contains(b)) {
                    int z = a + b;
                    a = b;
                    b = z;
                    count++;
                }
                ans = Math.max(ans, count);
            }
        }
        return ans < 3 ? 0 : ans;        
    }
}

动态规划解法

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            indexMap.put(arr[i], i);
        }
        // 由暴力解法可以看出，后面的斐波拉契数列是否能成立，依赖于前面的计算结果。
        // 这种就适合动态规划，毕竟算法的思想就是有记忆的递归。
        // 这个最长子序列能想到动态规划，但更多地是想着是一维数组去解
        // dp定义,以i,j位置为末尾的元素，对应的最长的斐波拉契子序列的长度
        int[][] dp = new int[len][len];
        int ans = 0;
        for (int i = 1; i < len; i++) {
            // 这里倒序遍历，可以依赖上一轮计算结果, 后面的arr[j] * 2 > arr[i]必不可少，不然
            // 会出现k大于j的情况
            for (int j = i - 1; j >= 0 && arr[j] * 2 > arr[i]; j--) {
                int diff = arr[i] - arr[j];
                int k = indexMap.getOrDefault(diff, -1);
                if (k >= 0) {
                    dp[j][i] = Math.max(dp[k][j] + 1, 3);
                }
                ans = Math.max(dp[j][i], ans);
            }
        }
        return ans;
    }
}