NYOJ 214 單調遞增子序列(二)：O(N log N) LIS 經典解法

問題描述

給定長度 N (≤ 100,000) 的整數序列，求最長嚴格遞增子序列（LIS）的長度。多組測試數據，以 EOF 結束。

經典 DP + 二分優化

定義 dp[len] 為長度為 len 的遞增子序列的最小末尾值。遍歷序列每個元素 x：

• 若 x > dp[maxLen]，則 maxLen++，dp[maxLen] = x。
• 否則，在 dp[1..maxLen] 中二分查找第一個 ≥ x 的位置 pos，更新 dp[pos] = x。

代碼實現

int BinarySearch(int x, int len, const vector& dp) {
    int l = 1, r = len;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (dp[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector a(n), dp(n + 1);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        int len = 0;
        for (int x : a) {
            int pos = BinarySearch(x, len, dp);
            dp[pos] = x;
            if (pos > len) len = pos;
        }
        printf("%d\n", len);
    }
    return 0;
}

關鍵點總結

1. dp 數組存儲的是「可能的最小末尾值」，而非真實子序列，但長度正確。
2. 二分查找條件為 dp[mid] < x 移動左邊界，確保找到第一個 ≥ x 的位置，保證嚴格遞增。
3. 時間複雜度 O(N log N)，空間 O(N)，滿足 N=100,000 要求。

延伸思考

若需輸出具體的一條 LIS，需額外維護前驅指針與位置記錄，並在最後回溯構造。本題僅求長度，故簡化版本足矣。