最長遞增子序列 (LIS) O(n log n) 算法完整講解與 C++ 實現

• 若 x > d[maxLen]，延長最長序列：d[++maxLen] = x。
• 否則，二分查找第一個 d[pos] >= x，更新 d[pos] = x（不增加長度，但優化了該長度的末尾值，利於後續延長）。

最終 maxLen 即 LIS 長度。

C++ 完整實現

#include 
using namespace std;

int LIS(const vector& a) {
    vector d;
    for (int x : a) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end()) d.push_back(x);
        else *it = x;
    }
    return (int)d.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << LIS(a) << '\n';
    return 0;
}

求每個位置結尾的 LIS 長度

在上述過程中，pos = lower_bound(...) - d.begin() + 1 即為以當前元素結尾的 LIS 長度。存入 lis[i] 可用於雙向 LIS（如山脈序列、Wavio Sequence）。

非嚴格遞增（允許相等）

將 lower_bound 改為 upper_bound（查找第一個 > x），即可求最長非嚴格遞增子序列長度。

複雜度分析

• 時間：O(n log n)，每個元素一次二分查找。
• 空間：O(n) 存儲 d 數組。

總結

LIS O(n log n) 算法是「動態規劃優化」的經典範例：狀態定義轉化為「末尾最小值」，利用單調性二分查找。模板極短，威力極大，是競賽與面試必備技能。延伸應用：最長非降子序列、最長山脈子序列、最小分割遞增子序列數（Dilworth 定理）、LCS 轉 LIS（當一序列為排列）等。