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

最长递增子序列

http://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481

思路

题目分析

题目首先给出了一个数组，要求在这个数组中找出仍然保留相对前后顺序，并且成递增规律的最长的子数组
我们首先需要有一个概念，这种求序列最长最短子序列的问题可以考虑动态规划，因为通常情况下都符合动态规划的子问题结构的特征，本题就可以从这个点入手。

处理最长递增子序列问题是典型的动态规划问题，因为该问题中存在子问题结构，当前的最长递增子序列可以由前面的转换，因此也有了状态转移方程
设定dp[i]表示包括arr[i]在内的最长递增子序列的长度
状态转移方程为：
$图片说明$

方法一：动态规划（双循环无优化）（超时未通过）

在对状态方程进行更新的时候采用双循环的方式，时间代价较高

class Solution {
public:
    /**
     * return the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        vector<int> dp(arr.size(), 1);                        //dp[i]表示以arr[i]结尾的最长递增子序列长度
        int mx = 1;
        for(int i = 1; i < arr.size(); i++) {
            for(int j = 0; j < i; j++) {
                //判断是否需要更新当前i结尾的最长递增子序列长度，是否要在原来的基础上+1
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {   //条件就是以后面的数字大，并且前面的最长递增子序列长度+1后比当前的最长递增子序列长度大
                    dp[i] = dp[j] + 1;
                    mx = max(mx, dp[i]);                     //记录最大长度
                }
            }
        }
        vector<int> res(mx);
        int i = dp.size() - 1;
        while(mx > 0 && i >= 0) {                            //倒序填到最终返会vector中正好是字典最小的
            if(dp[i] == mx) {
                res[--mx] = arr[i];
            }
            --i;
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O(N^2)$ ，采用了双循环的方式
空间复杂度： $O(N)$ ，使用额外的dp数组

方法二：贪心算法+二分优化（通过）

图片说明

我们在构建最终返回的列表时，采用贪心的思想，每次都取最小的排在前面，这样能最大限度地给后面留出放相对较大的数字的空间，这样才能达到我们长的子串的目的。
在遇到更小的数字i时候，我们所维护的返回的列表要更新进来这个更小的数字，将其替换掉在au数组辅助升序序列中第一个大于当前数字i的位置的数字，并且更新mx数组中对应的值，表示到当前数字i为止可以构成的最长的递增子序列的长度
最终当au和mx数组都构建完成后，通过对mx数组的逆序访问来确定哪些数字可以构成最长递增子序列。

class Solution {
public:
    /**
     * return the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        if(arr.size() == 0) return {};
        vector<int> au(1, arr[0]);               //au[i]表示长为i+1的递增序列中，结尾数字最小那个数字
        vector<int> mx(1, 1);                    //mx[i]表示以arr[i]结束的最长递增序列的长度
        for(int i = 1; i < arr.size(); i++) {
            if(arr[i] > au.back()) {             //当新的数字比我们维护的au最后一个数字还大，则需要直接添加到后面，最长的递增子序列长度直接+1 
                au.emplace_back(arr[i]);
                mx.emplace_back(au.size());
            }
            else {                               //当新的数字比我们维护的au最后一个数字还小，则调用二分搜索，替代前面某一个数字的位置
                int pos = lower_bound(au.begin(), au.end(), arr[i]) - au.begin();    //返回第一个大于arr[i]当前数字的位置
                au[pos] = arr[i];                                                    //用新的小数字替代这个位置的数字
                mx.emplace_back(pos + 1);
            }
        }

        //倒序输出按照字典序排序的最小的那个最长的递增子序列
        int i = arr.size() - 1;
        int mxLen = au.size();
        vector<int> res(mxLen);
        while(mxLen > 0 && i >= 0) {
            if(mxLen == mx[i]) res[--mxLen] = arr[i];
            --i;
        }
        return res;
    }
};