题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
解题
leetcode-1964：找出到每个位置为止最长的有效障碍赛跑路线 是这道题，增强版，对时间复杂度要求更高
方法一：动态规划
dp[i]表示i之前包括i的最长上升子序列的长度。
由于dp[i]包括i的最长递增子序列，可能在dp[0]~dp[i-1]都有可能，因此有2层循环
最后return的时候，也要取其中的最大值。
class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size()==0) return 0; vector<int> dp(nums.size(),1); for(int i=1;i<nums.size();i++){ for(int j=0;j<i;j++){ if(nums[i]>nums[j]){ dp[i]=max(dp[i],dp[j]+1); } } } return *max_element(dp.begin(),dp.end()); } };
方法二：动态规划+二分查找
dp[i]表示 长度为i+1的序列，序列最后一个数的最小值
class Solution { public: int lengthOfLIS(vector<int>& nums) { int res=0; int n=nums.size(); vector<int> dp(n+1,INT_MAX);//序列长度为i的，序列末尾最小的数字 dp[0]=INT_MIN;//任何一个数都应该比长度为0的序列末尾的数字大。 for(int i=0;i<n;i++){ int l=0,r=i+1; while(l<r){ int mid=(l+r)/2; if(nums[i]<=dp[mid]){//严格递增，要用<= ，非严格递增用 < r=mid; }else l=mid+1;//如果大于，应该去寻找更长的长度 } res=max(res,l); dp[l]=min(dp[l],nums[i]); } return res; } };
