这道题有个非常巧妙的方法：

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.

但是这道题取巧的点在于，计算的个数是正确的，但是计算的序列是错的，详细解释参考leetcode-300
中规中矩的解法还是需要动态规划DP，上面的解法一般正常人很难想到。
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;
    }
};

初始时将dp和res值均设置为1，从前往后遍历，需要判断当前第i+1个元素要大于前面的元素，然后判断包含当前元素后是否大于当前dp记录的最大值，由于动态规划方法复杂度为N的平方，因此运行效率较差：

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.

2021.02.28更新

尝试使用暴力破解方法，发现理解太片面，下面的暴力解法无法解决需要回退的场景，例如0,1,0,3,2,3，会错误的把0 1 3 当成最后的答案，看了之前的笔记发现方法一虽然巧妙，但比较难想到，中规中矩的解法还得动态规划。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int res = 0,n = nums.size();
        for(int i = 0;i < n;i++)
        {
            int loc = i,cnt = 1;
            for(int j = i+1;j < n;j++)
            {
                if(nums[j] > nums[loc])
                {
                    cnt++;
                    loc = j;
                }
            }

            res = max(res,cnt);
        }
        return res;
    }
};