``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i = 0;i < nums.size();i++)
{
auto it = lower_bound(res.begin(),res.end(),nums[i]);
if(it == res.end()){
res.push_back(nums[i]);
}
else
*it = nums[i];
}

return res.size();
}
};``````

``````Runtime: 16 ms, faster than 81.06% of C++ online submissions for Longest Increasing Subsequence.
Memory Usage: 10.8 MB, less than 30.81% of C++ online submissions for Longest Increasing Subsequence.``````

DP[ i ]表示从头开始包含第i个元素的最长上升子序列
DP[ i ] = max{DP[j]} ,0< j < i,且 a[ j ] < a[ i ],DP算法因为需要两个循环，因此复杂度N的平方。

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int size = nums.size(),res = 1;
//if(size <= 0) return 0;
vector<int> dp(size,1);

for(int i = 1; i < size;i++)
{
for(int j = 0;j < i;j++)
{
if(nums[j] < nums[i])
dp[i] = max(dp[i],dp[j] + 1);
}
res = max(res,dp[i]);
}

return res;
}
};``````

``````Runtime: 324 ms, faster than 22.07% of C++ online submissions for Longest Increasing Subsequence.
Memory Usage: 10.8 MB, less than 55.13% of C++ online submissions for Longest Increasing Subsequence.``````