300. 最长递增子序列 动态规划O(n2) 贪心+二分 O(nlogn)

本文主要是介绍300. 最长递增子序列 动态规划O(n2) 贪心+二分 O(nlogn)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

1. 动态规划，定义状态$dp[i]$代表以 $nums[i]$结尾的最长递增子序列的长度，这样的话$dp[i]$和其子问题$dp[k],0<=k<i$便产生了联系、
   • 状态转移方程$dp[i]=max(dp[k]+1),0<=k<iif(nums[i]>nums[k])$
   • 时间复杂度$O(n^2)$
   • 空间复杂度$O(n)$
2. 官方给的$O(nlogn)$的解法，采用贪心和二分。
   • 维护一个$d[]$数组，$d[i]$代表长度为$i$的最长递增子序列的最后一个数字的值，$len$代表当前得到的最长序列的长度。这样做是基于贪心的思想，我们希望我们的序列的数字增长的尽可能的慢，这样的话我们后面就可以尽可能多的增加数字。
   • 如果当前的数值$nums[i]>d[len]$，我们更新$d[++len]=nums[i]$，否则，我们需要更新$d$数组前面的数值，$d[]$数组在这里是单调递增的，如果$d[]$数组不是单调递增的，假设一个长度为$n$的递增子序列和一个长度为$n+1$的递增子序列,且有$d[n+1]<d[n]$，并且我们知道$d[n],d[n+1]$分别代表着长度为$n$和$n+1$的递增子序列，那么$d[n+1]$的倒数第二个数字肯定在$d[n]$这个数字要小，$d[n+1]和d[n]$之间只有一个数字长度的差距，$d[n]$显然应该不为$d[n]$而为$d[n+1]$所代表序列的倒数第二个数字。官方题解的证明。我们可以用二分查找的方式找到我们的满足条件$d[i-1]<=nums[j]<nums[i]$的$i$，我们去更新这个$d[i]$维护好$d[]$数组，这样最后的$d[len]$就是我们的答案了。

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

// 时间复杂度$O(n^2)$
class Solution {
public:vector<int>res;int lengthOfLIS(vector<int>& nums) {int n=nums.size();if(n==0){return 0;}res.resize(n,1);// res[0]=1;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j])res[i]=max(res[i],res[j]+1);}}int ans=res[0];for(int i=1;i<n;i++){ans=max(ans,res[i]);}return ans;}
};

// 时间复杂度O(nlogn)
class Solution {
public:vector<int>d;int len;int lengthOfLIS(vector<int>& nums) {int n=nums.size();if(n==0){return 0;}d.resize(n+1,0);len=1;                  // 当前的最长的单调递增子序列的长度d[0]=0,d[1]=nums[0];for(int i=1;i<n;i++){if(nums[i]>d[len]){d[++len]=nums[i];}else{int left=1,right=len;int mid;// 怎么找到数组中满足条件nums[i-1]<d[j]<=nums[i]的iint pos=0;while(left<=right){mid=(left+right)/2;if(d[mid]<nums[i]){pos=mid;left=mid+1;}else{right=mid-1;}}// 官方题解这里的写法不错d[pos+1]=nums[i];}}return len;}
};

这篇关于300. 最长递增子序列 动态规划O(n2) 贪心+二分 O(nlogn)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---