動態規劃求最長等差數列（LLAP）O(n²) 完整解析

問題定義

給定一個已排序的整數集合，找出其中最長等差數列（Longest Arithmetic Progression, LLAP）的長度。等差數列指任意相鄰兩項差值恆定的序列。

輸入: {1, 7, 10, 15, 27, 29}  → 輸出: 3  (如 {1, 15, 29}, 公差 14)
輸入: {5, 10, 15, 20, 25, 30} → 輸出: 6  (整個集合即為等差數列)

從簡單問題切入：判斷是否存在長度≥3的等差數列

固定中間元素 set[j]，尋找 set[i] (iset[k] (k>j) 使得 set[i] + set[k] == 2*set[j]。利用雙指針：

• i = j-1, k = j+1
• 若和過大 → i--；過小 → k++；相等 → 找到。
• 單次 j 掃描 O(n)，總複雜度 O(n²)。

動態規劃擴展：求最大長度

狀態定義

L[i][j] 表示以 set[i] 和 set[j] 為前兩項的最長等差數列長度（j > i）。

• 最後一列 L[i][n-1] = 2（任意兩項至少構成長度 2 的 AP）。
• 按 j 從右向左（n-2 ... 1）填表，確保 L[j][k] 已計算完成。

狀態轉移

固定 j，雙指針 i=j-1, k=j+1 搜尋：

• set[i] + set[k] < 2*set[j] → k++
• set[i] + set[k] > 2*set[j] → L[i][j] = 2; i--（無法形成更長 AP，基礎長度 2）
• == → L[i][j] = L[j][k] + 1（延續 j,k 的 AP），更新全域最大值，i--, k++ 繼續找同 j 的其他組合。

循環結束後，剩餘 i 設置 L[i][j] = 2。

複雜度

• 時間：O(n²) — 雙層迴圈（j + 雙指針掃描）。
• 空間：O(n²) — 二維 DP 表。可優化至 O(n) 空間（僅保留下一行），但代碼較繁瑣。

完整 Java 參考實現

public class LongestArithmeticProgression {
    // 判斷是否存在長度≥3的AP
    public static boolean arithmeticThree(int[] A, int n) {
        for (int j = 1; j < n-1; ++j) {
            int i = j-1, k = j+1;
            while (i >= 0 && k <= n-1) {
                int sum = A[i] + A[k];
                int target = 2 * A[j];
                if (sum == target) return true;
                else if (sum > target) --i;
                else ++k;
            }
        }
        return false;
    }

    // O(n²) DP 求 LLAP 長度
    public static int lengthOfLongestAP(int[] A, int n) {
        if (n <= 2) return n;
        int[][] L = new int[n][n];
        int llap = 2;
        for (int i = 0; i < n; ++i) L[i][n-1] = 2; // 最後一列初始化

        for (int j = n-2; j >= 1; --j) {
            int i = j-1, k = j+1;
            while (i >= 0 && k <= n-1) {
                int sum = A[i] + A[k];
                int target = 2 * A[j];
                if (sum < target) ++k;
                else if (sum > target) { L[i][j] = 2; --i; }
                else {
                    L[i][j] = L[j][k] + 1;
                    llap = Math.max(llap, L[i][j]);
                    --i; ++k;
                }
            }
            while (i >= 0) { L[i][j] = 2; --i; }
        }
        return llap;
    }

    public static void main(String[] args) {
        int[] A = {1, 7, 10, 15, 27, 29};
        System.out.println(arithmeticThree(A, A.length)); // true
        System.out.println(lengthOfLongestAP(A, A.length)); // 3
    }
}

關鍵洞察

1. 有序性是前提：未排序輸入需先 O(n log n) 排序。
2. DP 表填充順序：j 從右向左，保證 L[j][k] 就緒。
3. 雙指針單調性：利用陣列有序，i 只遞減、k 只遞增，無回溯。
4. 邊界條件：n <= 2 直接回傳 n。

來源：GeeksforGeeks - Length of LLAP in a sorted array