Description
![](https://kickstart.best/wp-content/uploads/2020/11/image-46-1024x879.png)
![](https://kickstart.best/wp-content/uploads/2020/11/image-47-1024x143.png)
Submission
O(n^2)
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); for(int i = 0; i < n; ++i) { for(int j = 0; j < i; ++j) { if(nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } } return *max_element(dp.begin(), dp.end()); } };
O(nlogn)
class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> q; int n = nums.size(); for(int i = 0; i < n; ++i) { auto iter = lower_bound(q.begin(), q.end(), nums[i]); if(iter == q.end()) { q.push_back(nums[i]); } else { *iter = nums[i]; } } return q.size(); } };