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

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.