如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

提示：

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 10^9

暴力（三层循环）

public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length, res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i];
                int b = arr[j];
                int count = 0;
                for (int k = j + 1; k < n; k++) {
                    if (a + b == arr[k]) {
                        count = count == 0 ? 3 : count + 1;
                        a = b;
                        b = arr[k];
                    } else if (a + b < arr[k]) {
                        break;
                    }
                }
                res = Math.max(res, count);
            }
        }
        return res;
    }

效率不好，但是能通过。

image.png

暴力 + 二分查找

 public static int lenLongestFibSubseq(int[] arr) {
        //从i开始，下一个是j
        int max = 2;
        for(int i = 0; i < arr.length; i++){
            for(int j = i + 1; j < arr.length; j++){
                int tmpI = arr[i];
                int tmpJ = arr[j];
                int sum = tmpI + tmpJ;
                int cur = 2;
                // 使用 binarySearch，底层是二分查找
                while(Arrays.binarySearch(arr, sum) >= 0){
                    tmpI = tmpJ;
                    tmpJ = sum;
                    sum = tmpI + tmpJ;
                    cur++;
                }
                max = Math.max(max, cur);
            }
        }
        return max < 3 ? 0 : max;
    }

效率有所改进，但还是很好。

image.png

动态规划

public static int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;;
        int res = 0, sum;
        int[][] dp = new int[n][n];
        //dp[i][j]表示以arr[i]、arr[j]结尾的子序列的最大斐波那契数列长度
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 2);
        }
        int l = 0, r = 0;
        for (int i = 2; i < n; i++) {
            l = 0;
            r = i - 1;
            while (l < r) {
                sum = arr[l] + arr[r];
                if (sum == arr[i]) {
                    dp[r][i] = Math.max(dp[r][i], dp[l][r] + 1);
                    res = Math.max(res, dp[r][i]);
                    l++;
                    r--;
                } else if (sum < arr[i]) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }

image.png

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。