题目如下

数据范围

这道题用暴力的角度来做的话时间复杂度是O(2^n)结合数据范围来看显然会超时。
那么我们可以考虑动态规划：
令dp[i]是以nums[i]为结尾的递增子序列的长度那么dp[i] = max(dp[j] + 1,dp[i])其中0 <= j < i当然要满足nums[i] > nums[j]。
(dp初始值都是1因为每个数字都是长度为1的递增子序列)
如此我们可以写出代码

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