題目描述

給定無序整數數組，求最長上升子序列長度。示例：[10,9,2,5,3,7,101,18] → [2,3,7,101] 長度 4。要求 O(n²)，進階 O(n log n)。

方法一：動態規劃 O(n²)

dp[i] 表示以 nums[i] 結尾的最長上升子序列長度。轉移：dp[i] = max(dp[j]) + 1，對所有 j < i 且 nums[j] < nums[i]。最終答案 max(dp[i])。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;
        vector<int> dp(n, 1);
        int maxlen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            maxlen = max(maxlen, dp[i]);
        }
        return maxlen;
    }
};

若需輸出具體序列，另維護 pre[i] 記錄前驅索引。

方法二：貪心 + 二分查找 O(n log n)

維護有序數組 tails，其中 tails[len] 存儲長度為 len+1 的上升子序列的最小結尾值。遍歷數組：

• 若 num > tails.back()，追加到末尾（長度增加）
• 否則二分查找 tails 中第一個 ≥ num 的位置，替換之

直觀理解： 替換較大結尾值為較小值，不改變當前長度，但增加後續延伸潛力（貪心策略）。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int num : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), num);
            if (it == tails.end()) tails.push_back(num);
            else *it = num;
        }
        return tails.size();
    }
};

關鍵缺陷與證明

缺陷： tails 內容不一定是真實的 LIS（如 [1,5,8,2] → tails=[1,2,8] 非真實序列）。但長度正確。原因：

• num > tail 時長度 +1，必正確
• num ≤ tail 時替換，保持長度不變，但優化了結尾值，不影響最優解存在性

完整證明需用數學歸納法，核心不變量：tails[i] 是所有長度 i+1 上升子序列的最小結尾值。

擴展：輸出真實 LIS 序列

O(n log n) 下輸出真實序列較複雜，需額外維護前驅指針和歷史快照，或退回 O(n²) DP。面試中通常僅要求長度。