刚刚开始并没有发现子串和子序列的区别，所以出现了一些问题。发现是子序列之后就写不出来了。思路还是设定一个数组，存储以当前一位为结尾的最长子序列的长度，而该数组进行更新是需要对之前的所有位置进行遍历，如果当前节点的值大于遍历到的节点，则说明能够生成一个比所遍历到的最长子序列长一位的子序列。贴代码
1 class Solution { 2 public: 3 int lengthOfLIS(vector<int>& nums) 4 { 5 int n = nums.size(); 6 if(n<=0) 7 return 0; 8 vector<int> dp(n,0); 9 for(int i = 0 ; i < n ; i++) 10 { 11 dp[i] = 1; 12 for(int j = 0 ; j < i ; j++) 13 { 14 if(nums[i]>nums[j]) 15 dp[i] = max(dp[i],dp[j]+1); 16 } 17 } 18 return *max_element(dp.begin(),dp.end()); 19 } 20 };
贪心加上二分查找。最核心的想法在于，想要让上升序列长，就一定要让序列中的值尽可能的短。唯一一个增加序列长度的时候，就是当前值大于序列最大值的时候，其余的时候，找到序列中第一个小于当前值的位置，并进行替换，这一部分由二分查找完成。细节很多，贴代
1 class Solution { 2 public: 3 int lengthOfLIS(vector<int>& nums) 4 { 5 int len = 1; 6 int n = nums.size(); 7 if(n == 0) return 0; 8 vector<int> dp(n+1,0); 9 dp[len] = nums[0]; 10 for(int i = 1 ; i < n ; i++) 11 { 12 int temp = nums[i]; 13 if(temp>dp[len]) 14 { 15 dp[++len] = temp; 16 } 17 else 18 { 19 int l = 1; 20 int r = len; 21 int pos = 0; 22 while(l<=r) 23 { 24 int mid = (l+r)/2; 25 if(temp>dp[mid]) 26 { 27 pos = mid; 28 l = mid + 1; 29 } 30 else 31 { 32 r = mid - 1; 33 } 34 } 35 dp[pos+1] = temp; 36 } 37 } 38 return len; 39 } 40 };