如果序列 X_1, X_2, ..., X_n 滿足下列條件，就說它是 斐波那契式 的：

n >= 3
對于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
給定一個嚴格遞增的正整數(shù)數(shù)組形成序列 arr ，找到 arr 中最長的斐波那契式的子序列的長度。如果一個不存在，返回 0 。

（回想一下，子序列是從原序列 arr 中派生出來的，它從 arr 中刪掉任意數(shù)量的元素（也可以不刪），而不改變其余元素的順序。例如， [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

暴力（三層循環(huán)）

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

動態(tài)規(guī)劃

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]結(jié)尾的子序列的最大斐波那契數(shù)列長度
        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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。