C++ Solution with two different versions: DP with O(n^2) time and BinearySearch with O(nlgn) time

• ``````/*
* DP, O(n^2) Time & O(n) Space
*/
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int ans = 1;
if(nums.size() < 2)
return nums.size();
vector<int> dp(nums.size() + 1);
for(int i = 0; i < nums.size(); ++ i)
dp[i] = 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);
}
ans = max(ans, dp[i]);
}
return ans;
}
};

/*
* Bineary Search, O(nlgn) time and O(n) space
*/
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int ans = 0;
if(nums.size() < 2)
return nums.size();
vector<int> stk(nums.size() + 1);
for(int i = 0; i < nums.size(); ++ i){
bsearch(ans, nums[i], stk);
}
return ans;
}
private:
void bsearch(int &ans, int val, vector<int> &stk){
if(ans == 0 || val > stk[ans - 1]){
stk[ans ++] = val;
return ;
}
if(val <= stk[0]){
stk[0] = val;
return ;
}
int l = 0, r = ans - 1, id;
while(l <= r){
int mid = (l + r)>>1;
if(stk[mid] == val)
return;
else if(stk[mid] < val){
id = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
stk[l] = val;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.