HDU 1950：最長上升子序列 (LIS) 經典應用——信號布線無交叉最大數

• 若 x > d[len]，延長序列：d[++len] = x。
• 否則，在 d[1..len] 中二分查找第一個 ≥ x 的位置 pos，更新 d[pos] = x（不改變長度，但優化結尾值，利於後續延長）。

d 陣列始終嚴格遞增，故可用二分查找。最終 len 即為 LIS 長度。

演示過程

序列：3 2 4 6 5 7 3

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 40005;
int a[MAXN], d[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int p; scanf("%d", &p);
        for (int i = 0; i < p; ++i) scanf("%d", &a[i]);
        int len = 0;
        for (int i = 0; i < p; ++i) {
            int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
            d[pos] = a[i];
            if (pos > len) len = pos;
        }
        printf("%d\n", len);
    }
    return 0;
}

手寫二分版本 (無 STL)

int pos = 1, l = 1, r = len;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (d[mid] < a[i]) pos = mid + 1, l = mid + 1;
    else r = mid - 1;
}
d[pos] = a[i];
if (pos > len) len = pos;

複雜度

• 時間：O(p log p)，p ≤ 40000，極快。
• 空間：O(p)。