• 若 a[i] > d[max_len]，延長：d[++max_len] = a[i]。
• 否則二分查找第一個 d[pos] ≥ a[i]，更新 d[pos] = a[i]。

最終 max_len 即 LIS 長度。d 數組始終嚴格遞增，保證二分有效性。

代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int a[MAXN], d[MAXN];

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

關鍵點解析

1. lower_bound 返回第一個 ≥ a[i] 的位置，對應「非嚴格遞增」子序列（允許相等）。若要求嚴格遞增，用 upper_bound（第一個 > a[i]）。
2. d 數組只存結尾值，不存實際序列。若需輸出具體 LIS，需額外記錄前驅指針。
3. 初始 len=0，d 無需初始化，lower_bound 會正確返回 0。
4. 多測試用例循環讀取直到 EOF。

變體：非嚴格遞增 / 非嚴格遞減

• 非嚴格遞增（允許相等）：lower_bound（≥）
• 嚴格遞增：upper_bound（>）
• 非嚴格遞減：反轉數組或取反後求 LIS

複雜度

• 時間：O(n log n)，n=100000 约 170 萬比較，極快。
• 空間：O(n)。

總結

POJ 3903 是 LIS O(n log n) 算法的標準模板題。核心思想：用 d[len] 記錄「長度為 len 的最小結尾」，貪心地保持結尾盡可能小以便後續延長。二分查找定位更新位置，lower_bound/upper_bound 選擇決定嚴格/非嚴格。背熟此模板，所有 LIS 變體迎刃而解。