题解 | #最长上升子序列(一)#

题目主要信息:

• 给定一个数组，求其中最长的严格上升子序列的长度
• 子序列是指数组去掉或不去掉元素后的数组，不要求在原本数组中全部相邻，但是在原数组中的相对位置不能改变
• 严格上升指子序列严格单调递增

具体思路:

要找到最长的递增子序列长度，常用方法是动态规划，用$dp[i]dp[i]$表示到元素$ii$结尾时，最长的子序列的长度，第一层遍历得到n个长度的子串，第二层遍历该子串求相应到元素$ii$结尾时的最长递增序列长度，期间维护最大值。

• 初始条件： 不管如何只要数组不为空，最长递增子序列至少有1个，因此可以初始化dp数组全部为1.
• 转移方程： 对于每一个到$ii$结尾的子串，如果遍历过程中遇到元素j小于结尾，说明以该元素结尾的子序列加上子串末尾元素也是严格递增的，因此转移方程为$dp[i]=dp[j]+1dp[i]\; =\; dp[j]\; +\; 1$。

具体过程可以参考如下图示：

代码实现:

class Solution {
public:
    int LIS(vector<int>& arr) {
        vector<int> dp(arr.size(), 1); //设置数组长度大小的动态规划辅助数组
        int res = 0;
        for(int i = 1; i < arr.size(); i++){
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1; //i点比j点大，理论上dp要加1
                    //但是可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                    res = max(res, dp[i]); //找到最大长度
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，两层遍历循环
• 空间复杂度：$O(n)O(n)$，辅助数组dp的空间