算法精講：最長上升子序列（LIS）O(n²) DP 與 O(n log n) 貪心+二分雙解法 C++ 實現

算法精講：最長上升子序列（LIS）O(n²) DP 與 O(n log n) 貪心+二分雙解法 C++ 實現

最長上升子序列（Longest Increasing Subsequence, LIS）是動態規劃與貪心策略完美結合的經典問題。本文提供 O(n²) 標準 DP、O(n log n) 尾值數組+二分優化兩種核心解法，並延伸至路徑重構、非嚴格遞增、在線處理等變體。

問題形式化

• 輸入：長度為 n 的數列 a[0..n-1]
• 目標：找到最長嚴格遞增子序列長度（元素可不連續）
• 示例：n=5, a={4,2,3,1,5} → LIS={2,3,5} 長度 3

方案一：標準動態規劃 O(n²) 時間 O(n) 空間

狀態定義

dp[i] = 以 a[i] 結尾的最長上升子序列長度

遞推關係

dp[i] = 1 + max{ dp[j] | 0 ≤ j < i 且 a[j] < a[i] }
// 無滿足條件 j 時 max 為 0，dp[i] = 1

代碼實現

#include <stdio.h>
#include <algorithm>
#include <climits>

#define MAX_N 10000

int n;
int a[MAX_N];
int dp[MAX_N];

int lis_dp() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        res = std::max(res, dp[i]);
    }
    return res;
}

int main() {
    n = 5;
    int a1[] = {4, 2, 3, 1, 5};
    memcpy(a, a1, sizeof(a1));
    printf("result = %d\n", lis_dp());  // 3
    return 0;
}

方案二：貪心 + 二分優化 O(n log n) 時間 O(n) 空間（面試/競賽標準）

核心洞察

維護數組 tails[k] = 長度為 k+1 的所有上升子序列中，最小結尾元素。
tails 單調遞增 → 可二分查找。

算法流程

1. 遍歷 a[i]
2. 在 tails[0..len-1] 中二分查找第一個 ≥ a[i] 的位置 pos
3. 若 pos == len，a[i] 可延長最長子序列 → tails[len++] = a[i]
4. 否則 tails[pos] = a[i]（用更小值優化同長度子序列結尾）
5. 最終 len 即 LIS 長度

代碼實現

#include <stdio.h>
#include <algorithm>
#include <climits>

#define MAX_N 10000

int n;
int a[MAX_N];
int tails[MAX_N];  // tails[i] = 長度 i+1 的 LIS 最小結尾值

int lis_nlogn() {
    int len = 0;
    for (int i = 0; i < n; i++) {
        // lower_bound: 第一個 ≥ a[i] 的位置
        int pos = std::lower_bound(tails, tails + len, a[i]) - tails;
        tails[pos] = a[i];
        if (pos == len) len++;
    }
    return len;
}

// 手寫二分版（無 STL 環境）
int lower_bound_manual(int *arr, int len, int target) {
    int l = 0, r = len;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (arr[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;
}

路徑重構：輸出具體 LIS 序列（需 O(n²) DP 輔助）

// O(n²) DP 版天然支持路徑重構
int pre[MAX_N];  // 前驅索引

int lis_dp_with_path() {
    int res = 0, last = -1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1; pre[i] = -1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if (dp[i] > res) {
            res = dp[i];
            last = i;
        }
    }
    // 回溯輸出
    int seq[MAX_N], cnt = 0;
    for (int cur = last; cur != -1; cur = pre[cur])
        seq[cnt++] = a[cur];
    for (int i = cnt-1; i >= 0; i--)
        printf("%d ", seq[i]);
    printf("\n");
    return res;
}

變體擴展

複雜度對比與選型

手寫二分模板（背誦級）

// 返回第一個 ≥ target 的下標 [0, len]
int lower_bound(int *a, int len, int target) {
    int l = 0, r = len;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 返回第一個 > target 的下標 [0, len]
int upper_bound(int *a, int len, int target) {
    int l = 0, r = len;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > target) r = mid;
        else l = mid + 1;
    }
    return l;
}

經典測試用例

# 單調遞增
5
1 2 3 4 5
→ 5

# 單調遞減
5
5 4 3 2 1
→ 1

# 隨機
8
10 9 2 5 3 7 101 18
→ 4 (2,3,7,101 或 2,5,7,101)

# 重複元素 (嚴格遞增)
6
1 2 2 3 3 4
→ 4 (1,2,3,4)

# 非嚴格遞增
6
1 2 2 3 3 4
→ 6 (1,2,2,3,3,4)

LIS 問題展示了「狀態定義決定複雜度」的算法哲理：O(n²) DP 狀態「以 i 結尾」自然但冗餘；O(n log n) 狀態「長度 k 的最小結尾」極致壓縮信息。徹底掌握 tails 數組單調性證明與 lower_bound 替換邏輯，是演算法面試與競賽的必殺技。