最长上升子序列(二)

题意

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

方法

深搜(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>& a) {
        int ans = 0;
        for(int i =0 ;i<a.size();i++){ // 选择序列头部
            ans = max(ans,dfs(a,i,1));
        }
        return ans;
    }
};

复杂度分析

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

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

动态规划

分析

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

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

对于$ii$如果直接从当前位置向前搜索，那么每次的时间复杂度为$nn$, 对于题目的数据范围是会超时的

如果能更快的找到比当前位置小的又是最长的就好了

考虑一个辅助数组$len2val[i]len2val[i]$表示长度为$ii$的序列的最小的结束的值

这样的辅助数组一定是严格单调递增的

证明：

归纳法

如果当前数组是严格单调递增的，那么当**第$ii$个值，

如果它与数组中某个值相等，则不更新数组依然严格单调递增

如果它在数组中两个值之间，, 那么它更新了 $len2val[i+1]len2val[i+1]$, 数组依然严格单调递增

证毕

有了严格单调递增的辅助数组，就可以利用二分进行优化搜索效率了

样例

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

所以最后输出4即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& a) {
        const int INF = 0x3f3f3f3f;
        vector<int> len2val(a.size(),INF); // 长度最小值
        int ans = 0;
        for(int i =0 ;i<a.size();i++){ 
            int idx = lower_bound(len2val.begin(), len2val.end(), a[i]) - len2val.begin(); // 二分找第一个比a[i]大的
            len2val[idx] = a[i]; // 更新辅助数组
            ans = max(ans,idx+1);
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 计算每个位置的最大长度，需要二分搜索辅助数组，所以时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$

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