Longest Increasing Subsequence (LIS)

1. State Representation

维护所有非劣状态（Pareto Frontier）：

• a：递增子序列的结尾值（tail）。
• ℓ_a：该子序列的长度。

对于新元素 b，希望接到结尾小于 b 的最长 subsequence 后面：

如果没有合法前驱，最大值视为 0，单个元素构成长度为 1 的 subsequence。

2. Greedy — Dominance Pruning

如果两个状态满足：

那么 (a, ℓ_a) dominates (b, ℓ_b)。因为前者：

• 长度不短于后者。
• 结尾不大于后者，更容易被未来元素扩展。

因此可以安全删除 (b, ℓ_b)。

维护 Pareto Frontier 后：

且这些长度恰好为 \(1,2,\ldots,L\)。所以 prev(lower_bound(b)) 就是最优前驱；如果没有比 b 更小的 tail，就从长度 1 开始。

3. My Derivation — std::set + Pareto Frontier

这是我最初从 Greedy + Dominance Pruning 推导出来的版本：不用预先知道 tails 的结构，直接把状态 (tail, length) 放进有序集合， 让 std::set 维护所有非劣状态。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        /*
        10 9 5 3 7 101 18 1 2
        10->1
        9->1
        */

        set<pair<int, int>> st; // end_pt, len
        for(int x: nums){
            auto it = st.lower_bound(pair<int, int>{x, 1});
            if(it == st.begin()){
                if(it != st.end()) st.erase(it);
                st.insert({x, 1});
            }else{
                int len = prev(it)->second + 1;
                if(it != st.end()) st.erase(it);
                st.insert({x, len});
            }
        }

        int ret{};
        for(auto [_, l]: st){
            ret = max(ret, l);
        }
        return ret;
    }
};

这里的 Greedy 更新规则：

1. st.lower_bound({x, 1}) 找到 第一个 tail ≥ x 的状态； 因为 std::pair 按字典序比较，且合法长度都至少为 1，所以可以这样查询。
2. 如果它就是 begin()，说明没有合法前驱，插入 (x, 1)。
3. 否则，用 prev(it)->second + 1 得到最优长度，并插入新状态 (x, len)。
4. 如果 it != end()，只需要删掉 it： 它恰好对应新状态的同一个长度，但 tail 不小于 x，因此被新状态 dominate。

为什么只删一个就够？Frontier 上按 tail 排序时，长度正好是连续的 1, 2, ..., L。最优前驱的长度是 k，新状态的长度是 k+1； 它替换的正是原先长度为 k+1 的最小 tail。后续状态长度更长，不会被它 dominate。

例如处理 [10, 9, 5, 3, 7, 101, 18, 1, 2]： 在读到 18 时，Frontier 是 (3,1), (7,2), (18,3)； 之后 1 替换 (3,1)，2 替换 (7,2)， 最终最大长度仍为 3。

4. 从 TreeMap 到 Patience Sorting

定义：

对于每个新元素 x：

1. lower_bound(x)：找到第一个 tail >= x。
2. 如果存在，用 x 替换它（更新这一长度的最优结尾）。
3. 否则，新增一个 tail（LIS 长度增加）。

由于 tails 严格递增，可以直接 Binary Search。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;

        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }

        return tails.size();
    }
};

注意：tails 整个数组不一定对应某一条实际存在的 subsequence；但每个 tails[k] 都是某条长度为 k+1 的递增子序列的真实结尾。

5. Greedy vs DP

传统 DAG DP：

复杂度为 \(O(n^2)\)；无合法前驱时，最大值同样视为 0。

Patience Sorting 则通过 dominance pruning，避免枚举所有合法前驱。

6. Generalizable Insight

与 Monotonic Deque 类似，LIS 也是维护一个 Pareto Frontier：

Key takeaway：遇到优化问题时，不仅考虑如何 memoize，还要考虑：

Can one state dominate another for all possible future decisions?

如果能证明 dominance relation，就可能通过 Greedy Pruning 大幅压缩状态空间。