DP——最长上升子序列

较难题，超时，参考大佬的代码理清思路并重写一遍练习。
Rating:[5, 4, 5]

解法：dp

1.输入输出

输入：数组arr; n = |arr| <= 10^5
输出：数组ans，所有最长上升子序列中字典序最小的一个

根据输入规模，预估算法时间复杂度要小于O(n^2)。

2.递推方程

设 dp[i] 是以arr[i]为尾元素的最长子序列的长度。
dp[0] = 1;
dp[i] = max{dp[ j ]} + 1; j满足：(1) 0 =< j< i (2) arr[i]大于子问题dp[ j]的序列的结尾元素。

分析：
dp[j]可以通过遍历来寻找，然而这样算法总时间复杂度为O(n^2)。如何优化这一步是本题的一个关键。可以维护一个数组maxEnd来实现。maxEnd[k]存储长度为k+1的子序列的尾元素的最小值。那么当前的最长序列长度L=maxEnd.size()。维护maxEnd的步骤如下：

1. 若arr[i] > maxEnd.back() (尾元素)，dp[i] = L + 1, 将arr[i]插入maxEnd最后
2. 否则，在maxEnd中查找第一个比它大（或相等）的元素，将该值变更为dp[i]

对于2的思考：
设 maxEnd[k-1]< dp[i] < maxEnd[k]，那么dp[i]可以接在以maxEnd[k-1]为尾元素的序列之后，构成长度等于以maxEnd[k]为尾元素的序列。维护maxEnd的定义maxEnd[k] 变为 dp[i]。

易证maxEnd为递增序列，因此采用二分查找。优化后总时间复杂度O(nlogn)。

3.解的追踪

本题关第二个关键。由dp可得输入序列的最大长度maxL而题目要求输出这个序列。方法是从后向前遍历数组dp。设最后一个元素的是arr[k]，则dp[k]是遍历时遇到的第一个等于maxL的值。遇到的第一个下标等于maxL-1的值对应倒数第二个元素，依此类推。

正确性思考：
假设存在结尾在s前边的子序列s'，其长度和s相等但是字典序比s小。

1. 如果s'的尾元素比s的尾元素小，但前缀部分相等，那么s的尾元素接在s'后可以形成一个更长的子序列，矛盾。
2. 若s'的尾元素大于等于s的尾元素，但是前缀部分比s的前缀要小，则显然s尾接在s'的前缀部分可形成一个长度相等但是字典序更小或相等的序列。那么此处选取s的尾元素一定没错。

参考代码：

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    int search(int l, int r, int t, vector<int>& vec) {//在有序的vec[i, r)里二分查找t。查到返回下标；没查到返回第一个比t大的元素的下标。可用STL lower_bound替换。
        while (l < r) {
            int mid = (l + r) / 2;
            //保证返回的标号对应的值不小于t
            if (vec[mid] <= t) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    vector<int> LIS(vector<int>& arr) {
        if (arr.size() < 2) return arr;
        vector<int> dp(arr.size(), 0); //dp[i]存储以arr[i]为尾元素的最长子序列的长度
        vector<int> maxEnd; //maxEnd[i]存储长度为i+1的子序列的最小尾元素
        dp[0] = 1; maxEnd.push_back(arr[0]); //递推初值
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] > maxEnd.back()) { // 大于maxEnd尾元素
                dp[i] = maxEnd.size() + 1;
                maxEnd.push_back(arr[i]); //更新
            }
            else { //小于maxEnd尾元素
                int idx = search(0, maxEnd.size(), arr[i], maxEnd);
                maxEnd[idx] = arr[i];
                dp[i] = idx + 1;
            }
        }
        //追踪解
        int len = maxEnd.size();
        vector<int> ans(len);
        for (int i = dp.size()-1; i >= 0; --i) {
            if (dp[i] == len) {
                ans[len - 1] = arr[i];
                --len;
            }
        }
        return ans;
    }
};

启发：

• 使用二分优化查找，前提想办法构造有序序列
• stl二分查找相关：lower_bound，upper_bound，binary_search
• 正确的追踪解：贪心策略的验证

相似问题

5545. 无矛盾的最佳球队