最长上升子序列(动态规划贪心+二分)

题目：

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

题解：

动态规划经典题：

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); if(n==0) return 0; vector<int> dp(n,1); int ans=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1); } ans=max(ans,dp[i]); } return ans; } };

贪心+二分： 维护一个len数组，下标表示子序列长度，存储的值表示为达到当前长度的最小数，可证len是单调递增的，对每一个nums，二分len数组，找到插入位置，更新len数组。

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); int ans=0; vector<int> len(n+1,INT_MAX); for(int i=0;i<n;i++) { int l=lower_bound(len.begin()+1,len.end(),nums[i])-len.begin()-1; len[l+1]=nums[i]; } int i=0; for(i=n;i>=1;i--) if(len[i]!=INT_MAX) break; return i; } };