-4-24 Leetcode 300.最长递增子序列

class Solution {public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if(n <= 1)return n;vector<int> dp(n+1,1);//初始化是1，单独的子串是一个字符int ans = 0;for(int i = 0;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 dp[n];最大值不一定时最后一个return ans;}};

class Solution {public:int lengthOfLIS(vector<int>& nums) {vector<int> mysk;int n = nums.size();if(n <= 1)return n;mysk.push_back(nums[0]);for(int i = 1;i < n;i++){if(mysk.back() < nums[i])mysk.push_back(nums[i]);else {auto it = lower_bound(mysk.begin(),mysk.end(),nums[i]);*it = nums[i];//可是这种算法不会出现，比如// 2,3,5,6,4,然后把4放到前面了吗？// 确实可以，但是不会让数组增长}}return mysk.size();}};