POJ 2533 Longest Ordered Subsequence：O(n²) DP 求最長上升子序列

問題描述

給定長度 ≤ 100,000 的序列，求最長嚴格遞增子序列 (LIS) 長度。注意：O(n²) 在此數據範圍會超時，實際需 O(n log n) 算法。此處講解基礎 DP 版本作為教學入門。

基礎 DP 遞推

int sum[100001];  // sum[i] 表示以 a[i] 結尾的 LIS 長度
for (int i = 1; i <= n; i++) {
    int best = 1;
    for (int j = 1; j < i; j++)
        if (a[j] < a[i] && sum[j] + 1 > best)
            best = sum[j] + 1;
    sum[i] = best;
}
// 答案為 max(sum[1..n])

O(n log n) 優化算法（生產必備）

維護 tail[len] 表示長度為 len 的 IS 末尾最小值，二分查找插入位置：

vector tail;
for (int x : a) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) tail.push_back(x);
    else *it = x;
}
int lis = tail.size();

複雜度對比

完整代碼（含優化版）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    vector a(n), tail;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    cout << tail.size() << '\n';
    return 0;
}