題目資訊

題目編號: 873
題目連結: Length of Longest Fibonacci Subsequence
主題: Array, Hash Table, Dynamic Programming

題目敘述

一個數列 $x_1, x_2, \ldots, x_n$ 是 類似費波那契的 如果：

$n \geq 3$
對於所有的 $i + 2 \leq 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 \leq arr.length \leq 1000$
$1 \leq arr[i] < arr[i + 1] \leq 10^9$

直覺

此問題要求在一個嚴格遞增的數組中找出最長的具有斐波那契樣式性質的子序列。每個子序列的項目，從第三項開始，必須是其前兩項的和。由於給定的數組嚴格遞增，此特性簡化了形成該序列所需潛在前驅的識別。

挑戰是如何有效地確定可以構成有效斐波那契樣式子序列的數對。動態規劃方法在這裡顯得合適，因為它可以基於先前解決的短子序列構建更長的子序列的解決方案。

解法

該方法利用動態規劃（DP）技術系統地探索數組中的潛在斐波那契樣式子序列。以下是演算法的詳細說明：

初始化：
- 我們定義一個二維動態規劃表 dp，其中 dp[j][i] 用於儲存以索引 j 和 i 結尾的最長斐波那契樣式子序列的長度。最初，每個值都設為 2，因為任意兩個元素形成一個基本子序列。
遍歷數組：
- 我們迭代每個可能的終點 i 作為子序列的末端，從數組的第三個元素（索引 2）開始，因為斐波那契樣式的序列至少需要三個元素。
- 對於每個 i，我們考慮從 i-1 到 1 的所有潛在倒數第二個元素 j。
確定前一個元素：
- 對於每個選定的數對 (j, i)，計算滿足斐波那契性質所需的前一元素 neededPrev：即 arr[k] + arr[j] = arr[i]，因此 neededPrev = arr[i] - arr[j]。
- 如果 neededPrev 不小於 arr[j]，則中斷循環，因為所有後續的 j 都將產生更大的 neededPrev，違反遞增順序特性。
檢查前一個元素的存在性：
- 利用二分搜尋（lower_bound）在可能的索引範圍內檢查 neededPrev 是否存在於索引 j 之前的數組中。
- 如果在索引 k 處找到，則意味著 arr[k] 以 arr[j] 和 arr[i] 形成有效的斐波那契樣式屬性。
更新動態規劃表：
- 將 dp[j][i] 更新為 dp[k][j] + 1，表示 Fibonacci 樣式子序列直到 i 的當前長度。
- 在迭代過程中記錄遇到的最大子序列長度為 maxLength。
結果評估：
- 在考慮所有可能的子序列後，返回 maxLength 如果它大於 2；否則，返回 0 表示未找到長度超過兩個的有效子序列。

此方法確保我們能有效地探索所有潛在的子序列並有效地捕捉到具有所需特性的最長子序列，同時滿足時間複雜度的限制。

程式碼

C++

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        
        // 建立一個2D DP表，初始化為每對至少儲存2
        vector<vector<int>> dp(n, vector<int>(n, 2));
        
        // 答案變數用來追蹤找到的最大長度
        int maxLength = 0;

        // 從陣列的第三個元素開始遍歷
        for (int i = 2; i < n; i++) {
            // 從i之前的一個元素開始，一直到陣列的開頭
            for (int j = i - 1; j > 0; j--) {
                // 計算Fibonacci性質所需的前一個元素
                int neededPrev = arr[i] - arr[j];
                
                // 如果前一個元素不小於當前元素，則中止
                if (neededPrev >= arr[j]) break;
                
                // 找出前一個元素在陣列中的位置
                auto it = lower_bound(arr.begin(), arr.begin() + j, neededPrev);
                
                // 檢查前一個元素是否存在
                if (it != arr.begin() + j && *it == neededPrev) {
                    int k = it - arr.begin(); // 前一個元素的索引

                    // 更新(j, i)的DP表
                    dp[j][i] = dp[k][j] + 1;
                    
                    // 用找到的長度更新maxLength
                    maxLength = max(maxLength, dp[j][i]);
                }
            }
        }
        
        // 如果最長的長度大於二，則返回該長度；否則返回0
        return maxLength > 2 ? maxLength : 0;
    }
};

Python

class Solution:
    def lenLongestFibSubseq(self, arr):
        n = len(arr)
        
        # 建立一個2D DP表格，初始化為每對至少存儲2
        dp = [[2] * n for _ in range(n)]
        
        # 回答變量，用來追蹤找到的最大長度
        maxLength = 0

        # 從數組的第三個元素開始迭代
        for i in range(2, n):
            # 從元素i的前一位迭代至數組開始
            for j in range(i - 1, 0, -1):
                # 計算斐波那契性質所需的前一個元素
                neededPrev = arr[i] - arr[j]
                
                # 如果前一個元素不小於當前元素，則中斷
                if neededPrev >= arr[j]:
                    break
                
                # 找出前一個元素在數組中的位置
                it = bisect.bisect_left(arr, neededPrev, 0, j)
                
                # 檢查前一個元素是否存在
                if it != j and arr[it] == neededPrev:
                    k = it  # 前一個元素的索引

                    # 更新DP表格對於(j, i)
                    dp[j][i] = dp[k][j] + 1
                    
                    # 使用找到的長度更新maxLength
                    maxLength = max(maxLength, dp[j][i])
        
        # 如果最長長度大於二，則返回；否則返回0
        return maxLength if maxLength > 2 else 0

複雜度分析

時間複雜度: $O(n^2 \log n)$
此演算法涉及兩個巢狀迴圈遍歷陣列 arr，外層迴圈從第三個元素跑到陣列結尾（$O(n)$ 次迭代），內層迴圈則從外層迴圈的當前位置向後迭代（$O(n)$ 次迭代）。在內層迴圈中，會調用 lower_bound 來找到所需的前一個元素，最壞情況下涉及對多達 $j$ 個元素進行二分搜尋，給予該操作 $O(\log n)$ 的複雜度。因此，整體的時間複雜度為 $O(n^2 \log n)$。
空間複雜度: $O(n^2)$
空間複雜度主要來自於2D動態規劃表 dp，其包含 $n \times n$ 個項目。每個項目代表以索引 $j$ 和 $i$ 結尾的最長類Fibonacci子序列的長度。因此，空間複雜度為 $O(n^2)$。

CS Note
En

Leetcode 873. Length of Longest Fibonacci Subsequence

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析