一、學習目標

• 會定義 LIS（Longest Increasing Subsequence） 與「嚴格遞增 vs 非嚴格遞增」的差異。
• 熟練兩種做法：
  • O(N²)：dp[i] = 以 i 結尾的 LIS 長度。
  • O(N log N)（耐心排序 / tails 法）：維護每個長度最小可能結尾。
• 知道 lower_bound / upper_bound 的選擇與正確性不變量。
• 了解如何重建一條 LIS（父指標 + 最佳位置）。

二、觀念說明

LIS 是什麼？

• 子序列：可刪除任意元素，不必連續，保留相對順序。
• 嚴格遞增：a[i1] < a[i2] < ... < a[ik]。
• 非嚴格（遞增/不降）：≤，題目若要求「不降」，做法會有一點差。

O(N²) 經典 DP

• 狀態：dp[i] = 以 i 為結尾的 LIS 長度。
• 轉移：dp[i] = max(dp[j] + 1)，對所有 j < i 且 a[j] < a[i]。
• 初值：dp[i] = 1。
• 答案：max(dp[i])。
• 時間 O(N²)，空間 O(N)。

O(N log N)（耐心排序 / tails 陣列）

• 維護一個遞增陣列 tails：
  • tails[len-1] = 長度為 len 的嚴格遞增子序列中，最小可能結尾值。
• 對每個數 x：在 tails 裡找第一個 ≥ x 的位置（lower_bound）來替換；若都小於 x 則把 x 追加在尾端。
• tails.size() 就是 LIS 長度。
• 為什麼對？ 不變量：更小的結尾給未來延長留下更多空間；替換不會縮短任何已存在的長度，只是讓該長度的結尾更優。
• 嚴格 vs 非嚴格：
  • 嚴格遞增（<）→ 用 lower_bound（找第一個 >= x）。
  • 不降（<=）→ 用 upper_bound（找第一個 > x）。

三、CSES實戰演練

題目1:Increasing Subsequence

原題:
https://cses.fi/problemset/task/1145

題意：
給長度 n 的序列，求「嚴格遞增」子序列的最長長度。（只需輸出長度）

解題思路：
O(N log N) tails（lower_bound）。

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i<n; i++) cin >> a[i];

    vector<long long> tails; // tails[len-1] = 長度 len 的最小結尾
    tails.reserve(n);

    for (int i = 0; i<n; i++) {
        long long x = a[i];
        // 嚴格遞增 → 找第一個 >= x 的位置
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << (int)tails.size() << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Longest Increasing Subsequence

原題:
https://leetcode.com/problems/longest-increasing-subsequence/description/

題意：
回傳 LIS 長度（嚴格遞增）。

解題思路：
提供兩版：O(N log N) 與 O(N²)。

解法1:O(N log N)（tails）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        tails.reserve(nums.size());
        for (int i = 0; i<nums.size(); i++) {
            int x = nums[i];
            // 嚴格遞增 → lower_bound
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }
        return tails.size();
    }
};

解法2:O(N²)（經典 DP）

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