DDL's homepage

最长上升子序列

发表于 分类于 Valine：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

解法1.动态规划

时间复杂度O($n^2$)

思路

f[i]表示以ith字符结尾的最长上升子序列长度

这道题难在状态转移的求解
f[i]=max(f[i-1],f[i-2],......)+1 前提条件是 f[j]<f[i] 才能构成上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int>f(n);
        for(int i=0;i<n;i++){
            f[i]=1; //表示只含当前字符的序列长度
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]) f[i]=max(f[i],f[j]+1);
            }
        }
        int res=0;
        for(auto c:f) res=max(res,c);
        return res;
    }

解法2 直接构造最长上升子序列

时间复杂度 $O(nlogn)$

开一个辅助数组 f[i] 表示最长上升子序列长度为i+1 中最小结尾值

eg. [1,2,4] ,[1,2,3]两个子序列长度都为3， 但是第一个子序列结尾值3<4 ，于是 f[2]=3;

这里面的思路背景是 在dp解法中 f[i]=max(f[j]+1) nums[j] 越小 那么对nums[i]限制就越小

两个最长上升子序列长度相同 那么子序列尾部值越小 越有可能构建成更加长的子序列

由于构造的辅助数组一定单调上升，因此可以通过二分查找来做。

1
2
3
4
5
6
7
8
9
10
int lengthOfLIS(vector<int>& nums) {
        int n=nums.size(),len=0;
        vector<int> f;
        for(auto c:nums){
            int p=lower_bound(f.begin(),f.end(),c)-f.begin(); 
            if(p==f.size()) f.push_back(c);//查找元素比辅助数组最大值还要大
            else f[p]=c;
        }
        return f.size();
    }

最好是通过一个 toy example 来给给面试官讲这个思路。