题解 | #最长递增子序列#

题意整理：:对于给出的数组，要从其中找到一个子序列，满足序列中的数字是单调上升的，在满足的子序列中找到长度最长的并进行输出。子序列是指一个数组删除若干元素，但不改变其他元素相对位置形成的序列
方法一：动态规划（超时）
核心思想：
定义为对前 个数中，以第 个数字结尾的最长上升子序列的长度，且必须被选取。
分析知最大上升序列需要满足 , 其中 。
对，可以由在之前且满足的状态转移得到
可得状态转移方程为：,其中 ，且.
在计算完成后，为了得到最长递增子序列，需要从后往前对dp数组进行一次遍历，找到符合条件的数填入答案中。由于的值绝对能在左侧找到更小值,故只需要选取第一次遇见的满足条件的数即可


核心代码：

class Solution {
public:
    vector<int> LIS(vector<int>& arr) {
        vector<int> dp(arr.size(), 1); 
        int maxn = 0, n = arr.size();
        for(int i = 1; i < n; ++i){
            //找到满足 j < i,arr[j] < arr[i],的最大dp[j]进行转移
            int res = 0;
            for(int j = 0; j < i; ++j){
                if(arr[i] > arr[j]) {
                    res = max(res, dp[j]); 
                }
            }
            dp[i] = res + 1;//加上arr[i]
            maxn = max(maxn, dp[i]); //找到最大长度
        }
        vector<int> ans(maxn);
        for(int i = n - 1, j = maxn; j > 0; --i){ 
            //逆向找到第一个满足所需大小的数
            if(dp[i] == j){ 
                ans[--j] = arr[i];//填入后继续寻找下一个数
            }
        }
        return ans;
    }
};

复杂度分析：
时间复杂度：，n为数组长度。动态规划的状态数为n，每个状态需要O(n)时间进行遍历，所以总的时间复杂度为
空间复杂度：,需要使用与输入数组等长的dp数组

方法二：动态规划+二分
核心思想：
方法一中代码的问题在于状态转移时需要的时间复杂度，可以使用贪心的思想进行优化。
贪心思路：
对于一个序列，如果想让上升子序列尽量的长，那么需要让序列上升的尽可能的慢，因为需要每次在上升子序列末尾添加的数字尽可能小。
举例说明：如对序列 。构建长度为3的上升子序列时，应该选择 而不是 .

代码实现：基于上述方法，可以维护一个数字 ,表示长度为 的最长上升子序列的末尾数字的最小值，同时使用 记录当前最长上升子序列的长度。由此方法构建的 数组关于 单调递增。若不为单调递增，既存在 , 且 ,则可以通过从尾部删除元素使得两序列长相等，而此时 仍大于 ，说明不满足最长上升序列的最小值，导出矛盾。
通过遍历数组 中的每个元素，并对 数组和 的值进行更新。
当 时，更新 ;
否则使用二分法找到满足 的下标进行更新。
由于需要返回该子序列，需要添加一个辅助数组 表示当前值对于 值。最后通过倒序遍历这个数组找出最长递增子序列
核心代码：

class Solution {
public:
    vector<int> LIS(vector<int>& arr) {
        int n = arr.size();
        vector<int> d(n + 1, -1), p(n);
        int len = 1;//初始化长度为1，元素为序列第一个数字
        d[len] = arr[0];
        p[0] = 1;
        for(int i = 1; i < n; ++i) {
            if(arr[i] > d[len]) {
                //此时将该数字添加到末尾
                d[++len] = arr[i];
                p[i] = len;
            } else {
                //二分查找恰好合适的位置
                int left = 1, right = len, pos = 0;
                while(left <= right) {
                    int mid = (left + right) / 2;
                    if(d[mid] < arr[i]) {
                        pos = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                //对该位置数字进行更新
                d[pos + 1] = arr[i];
                p[i] = pos + 1;
            }
        }
        vector<int> ans(len);
        //逆向查找对应序列值
        for(int i = n - 1; i >= 0; --i) {
            if(p[i] == len) {
                ans[--len] = arr[i];
            }
        }
        return ans;
    }
};

复杂度分析：
时间复杂度：，需要对 个状态进行更新，每次更新使用二分查找复杂度为 。最后需要时间遍历 数组，故总时间复杂度为
空间复杂度：,使用了 数组和 数组