POJ 2533 Longest Ordered Subsequence 詳解

題目：給定長度 N (≤1000) 的數列，求最長嚴格上升子序列（LIS）長度。數值 0~10000。

核心算法：貪心 + 二分（耐心排序）

維護陣列 d[len]：長度為 len 的上升子序列的最小結尾值。
遍歷數列 x：
- 若 x > d[maxLen]，延長：d[++maxLen] = x。
- 否則二分查找 d 中 第一個 ≥ x 的位置 pos，更新 d[pos] = x。
最終 maxLen 即 LIS 長度。
（若要求非嚴格上升，查找第一個 > x 的位置。）

參考代碼 (C++ / Python / Java)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    while (cin >> n) {
        vector d;
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            auto it = lower_bound(d.begin(), d.end(), x); // 嚴格上升：first >= x
            if (it == d.end()) d.push_back(x);
            else *it = x;
        }
        cout << d.size() << '\n';
    }
    return 0;
}

# Python
import bisect, sys
def solve():
    data = sys.stdin.read().split()
    if not data: return
    it = iter(data)
    out = []
    while True:
        try:
            n = int(next(it))
        except StopIteration:
            break
        d = []
        for _ in range(n):
            x = int(next(it))
            pos = bisect.bisect_left(d, x) # 嚴格上升
            if pos == len(d): d.append(x)
            else: d[pos] = x
        out.append(str(len(d)))
    sys.stdout.write('\n'.join(out))
if __name__ == '__main__':
    solve()

// Java
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            List d = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                int x = sc.nextInt();
                int pos = Collections.binarySearch(d, x);
                if (pos < 0) pos = -pos - 1; // lower_bound
                if (pos == d.size()) d.add(x);
                else d.set(pos, x);
            }
            System.out.println(d.size());
        }
    }
}

關鍵點總結

1. d 陣列單調遞增：保證二分查找正確性。
2. lower_bound 即 first ≥ x：對應嚴格上升（相等時替換，不延長）。
3. d[len] 含義：長度 len 的 LIS 最小結尾，而非具體某個 LIS 的結尾。
4. 不輸出具體序列：本題僅需長度，若需輸出序列，需額外記錄前驅與位置。

複雜度分析

面試延伸

• 輸出具體 LIS：維護 pos[i] 記錄 x 在 d 中的位置，pre[i] 記錄前驅下標，回溯重構。
• 最長非遞減子序列：用 upper_bound (first > x)。
• 最長公共上升子序列 (LCIS)：雙重循環 + DP，O(n²)。

總結

POJ 2533 是 LIS O(n log n) 算法的標準模板題。耐心排序思想將 LIS 問題轉化為維護「最小結尾值」陣列，配合二分查找實現對數級優化。此算法是演算法面試高頻考點，掌握其核心不變量（d 單調性、lower_bound 語義）至關重要。