LeetCode [300] Longest Increasing Subsequence

300. Longest Increasing Subsequence

Medium

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n==0) return 0; vector<int> dp(n, 1); int ret = 1; 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); } ret = max(ret, dp[i]); } return ret; } }; //https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ class Solution1 { public: int lengthOfLIS(vector<int>& nums) { //al[L-1] is the last element of the min L-length sequence //for each number n in nums, find the first element al[L-1] in al greater (or equal) than n //replace al[L-1] by n (so we can keep the min property of the L-length subsequence) vector<int> al; for(auto n:nums){ if(al.size()==0 || n>al.back()) al.push_back(n); else{ int l = 0, r = al.size()-1; while(l<=r){ int m = l+(r-l)/2; if(n<=al[m] && (m==l || al[m-1]<n)){ al[m] = n; break; }else if(n<al[m]){ r = m-1; }else{ l = m+1; } } } } return al.size(); } }; class Solution2 { public: int lengthOfLIS(vector<int>& nums) { vector<int> al; for(auto n:nums){ auto it = lower_bound(al.begin(), al.end(), n); if(it==al.end()) al.push_back(n); else *it = n; } return al.size(); } };