最長單調遞增子序列 (LIS)：O(n²) 動態規劃完整實現與解析

問題定義

給定長度為 n 的數列，找出最長的嚴格遞增子序列（不要求連續）。輸出長度及一個具體序列。

動態規劃狀態定義

• dp[i]：以第 i 個元素結尾的最長遞增子序列長度
• pre[i]：該最優序列中，第 i 元素的前驅下標（用於回溯構造序列）

狀態轉移方程

dp[i] = 1 + max{ dp[j] | j < i 且 a[j] < a[i] }   (若無符合 j 則 dp[i]=1)
pre[i] = argmax j

完整 Java 實現

import java.util.Scanner;

public class LIS {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] a = new int[n+1];
            int[] dp = new int[n+1];
            int[] pre = new int[n+1];
            
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextInt();
                dp[i] = 1;
                pre[i] = 0;
            }
            
            // 從後向前 DP (亦可正向)
            for (int i = n-1; i >= 1; i--) {
                int maxLen = 0, bestJ = 0;
                for (int j = i+1; j <= n; j++) {
                    if (a[i] < a[j] && dp[j] > maxLen) {
                        maxLen = dp[j];
                        bestJ = j;
                    }
                }
                if (bestJ != 0) {
                    dp[i] = dp[bestJ] + 1;
                    pre[i] = bestJ;
                }
            }
            
            // 找全局最大
            int maxLen = 0, start = 0;
            for (int i = 1; i <= n; i++) {
                if (dp[i] > maxLen) {
                    maxLen = dp[i];
                    start = i;
                }
            }
            
            System.out.println("最長長度：" + maxLen);
            System.out.print("最長遞增序列：");
            for (int p = start; p != 0; p = pre[p])
                System.out.print(a[p] + " ");
            System.out.println();
        }
        sc.close();
    }
}

C++ 版本 (競賽常用)

#include 
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector a(n+1), dp(n+1, 1), pre(n+1, 0);
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; j++)
                if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
        
        int len = 0, pos = 0;
        for (int i = 1; i <= n; i++)
            if (dp[i] > len) { len = dp[i]; pos = i; }
        
        vector seq;
        for (int p = pos; p; p = pre[p]) seq.push_back(a[p]);
        reverse(seq.begin(), seq.end());
        
        cout << "Length: " << len << "\nSequence: ";
        for (int x : seq) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

複雜度分析

O(n log n) 優化算法 (二分 + 貪心)

維護數組 tails[len]：長度為 len 的遞增子序列的最小結尾值。對每個 x，二分查找第一個 ≥ x 的位置替換，或 append。最終 tails 長度即 LIS 長度。無法直接輸出具體序列（需額外記錄）。

// 僅求長度 O(n log n)
int lis_length(vector& a) {
    vector tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}