最长上升子序列(一)

题意

给定一个正整数数组，求它的最长上升子序列的长度

方法

深搜(TLE)

分析

选一个位置开始，作为上升序列的起点，从这个位置向后找比它大的数。

以此递归，每次记录长度，并记录所有方案中的最大长度，就是要求的值。

变成伪代码就是

dfs(当前位置i,当前上升序列长度cnt):
	for j = i+1 -> arr.length(): // 从当前位置向后
		if arr[j] > arr[i]: // 找一个比当前大的
            dfs(j,cnt+1) // 递归， 计数+1

代码

class Solution {
public:
    // 数组 当前下标 计数
    int dfs(vector<int>& arr,int idx,int cnt){
        int ans = cnt;
        for(int j = idx+1;j<arr.size();j++){ // 从当前位置向后
            // 找到比当前位置大的
            if(arr[j] > arr[idx]){ // 找一个比当前大的
                ans = max(ans,dfs(arr,j,cnt+1)); // 递归， 计数+1
            }
        }
        return ans;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        int ans = 0;
        for(int i =0 ;i<arr.size();i++){ // 选择序列头部
            ans = max(ans,dfs(arr,i,1));
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 最坏情况，相当于枚举了所有组合，所以总时间复杂度为$O(2^n)O(2^n)$

空间复杂度: 空间主要消耗在递归层数，递归层数不超过数组长度，所以空间复杂度为$O(n)O(n)$

动态规划

分析

上面的深搜方法，对较深的位置，有大量的重复搜索，而实际上，从一个位置开始，向后的最长上升序列长度是唯一的值，反过来讲，即是只需要关心这个位置前面部分的最长上升序列的长度。

于是用dp[i]表示，从开头到i且选则i的最大上升序列长度

样例

以题目样例数据[6,3,1,5,2,3,7]为例

所以最后输出4即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        if(arr.size() == 0)return 0;
        vector<int> dp(arr.size(),1); // 从开头到`i`且选则`i`的最大上升序列长度
        int ans = 1;
        for(int i = 1 ;i<arr.size();i++){ // 枚举每个位置
            for(int j = 0 ;j<i;j++){ // 找它前面比它小的点
                if(arr[j] < arr[i]){
                    dp[i] = max(dp[i],dp[j]+1); // 更新最长距离
                    ans = max(ans, dp[i]); // 更新答案
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 计算每个位置的最大长度，需要向前遍历一次数组，所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 用来记录每个位置最大长度的辅助数组与原数组长度相等，所以空间复杂度为$O(n)O(n)$