NYOJ 214 最長單調遞增子序列：O(n log n) 二分優化 DP 詳解

問題描述

給定長度 n (≤ 100,000) 的整數序列，求**最長單調遞增子序列（LIS）**的長度。多組測試數據，以 EOF 結束。樣例：`1 9 10 5 11 2 13` → LIS 為 `1 9 10 11 13`，長度 5。

從 O(n²) DP 到 O(n log n) 貪心+二分

經典 DP：`dp[i]` 表示以第 i 個元素結尾的 LIS 長度，轉移 `dp[i] = max(dp[j]) + 1 (j < i, a[j] < a[i])`，雙重循環 O(n²)，n=1e5 會 TLE。

關鍵觀察

對於相同長度的遞增子序列，**結尾元素越小，越容易向後延伸**。因此維護一個數組 `f[len]`：長度為 `len` 的遞增子序列的**最小結尾值**。`f` 單調嚴格遞增。

算法流程

1. `f[1] = a[1]`，`len = 1`。
2. 遍歷 `a[2..n]`：
   • 若 `a[i] > f[len]` → 可延伸最長子序列，`f[++len] = a[i]`。
   • 否則 → 在 `f[1..len]` 中**二分查找**第一個 `≥ a[i]` 的位置 `pos`，更新 `f[pos] = a[i]`（不增加長度，但優化了該長度的結尾值）。
3. 最終 `len` 即為 LIS 長度。

完整代碼（含負數處理）

#include 
#include 
#include 
#include 
#define M 100010
using namespace std;

int a[M], f[M];

int main() {
    int n;
    while (cin >> n) {
        int len = 0;
        // f[0] 設為 INT_MIN 處理負數情況
        f[0] = 0x80000000;  // -2^31
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if (a[i] > f[len]) {
                f[++len] = a[i];
            } else {
                // 二分查找第一個 >= a[i] 的位置
                int l = 1, r = len, pos = len;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (f[mid] >= a[i]) { pos = mid; r = mid - 1; }
                    else l = mid + 1;
                }
                f[pos] = a[i];
            }
        }
        printf("%d\n", len);
    }
    return 0;
}

關鍵細節解析

• 初始化 `f[0] = INT_MIN`：原代碼用 `1<<31`，確保任何負數都能通過 `a[i] > f[0]` 進入 `f[1]`，避免二分死循環。
• 二分查找下界：`lower_bound` 語義，C++ 可直接用 `lower_bound(f+1, f+len+1, a[i]) - f`。
• 不輸出具體序列：本題僅求長度，`f` 數組不保存真實 LIS，如需輸出序列需額外記錄前驅。
• 複雜度：O(n log n) 時間，O(n) 空間，n=1e5 輕鬆通過。

擴展：非嚴格遞增（允許相等）

將判斷條件 `a[i] > f[len]` 改為 `a[i] >= f[len]`，二分查找改為 `upper_bound`（第一個 `> a[i]` 的位置）。

總結

LIS 的 O(n log n) 算法是「貪心維護最優結尾值 + 二分查找」的經典範例。核心洞見：**同長度下結尾越小越優**。掌握此模板，可解決導彈攔截、建橋、俄套娃等大量變體問題。