用递归DFS遍历所有组合肯定积分会超时，原因是有很多重复的操作，可以想象每次回溯后肯定会有重复操作。所以改用动态规划。建立一个vector<int>memo,初始化为1，memo[i]表示以第i个数字结尾的最长上升子序列的。每次a把当前数字当作是最后一个序列的最后一个数字，只看这个数字之前的数字，如果比他之前的数字大，那么选择这个数字之后最大上升序列长度+1，memo[i]=memo[j]+1.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()!=)
{
vector<int>memo(nums.size() + , );
int i;
int j;
for (i = ; i <= nums.size() - ; i++)
{
for (j = ; j < i; j++)
{
if (nums[i] > nums[j])
{
if (memo[i] < memo[j] + )
{
memo[i] = memo[j] + ;
}
}
}
}
sort(memo.begin(), memo.end());
return memo[memo.size() - ];
}
else
return ;
}
};
---恢复内容结束---