Input
10 9 2 5 3 7 101 18
Output
4 （因为2,3,7,101是最长的递增子序列）
解题思路
该问题满足最优子结构性质，因此可以使用动态规划求解。
定义如下符号：
-
表示问题序列的总长度。
-
表示下标从1到i的一个序列，特别地，
表示下标从1开始，长度为n的一个序列，也就是问题的输入。
-
表示
个元素。
由于问题的最优解必然对应某个子序列，而这个子序列又必然由某个结尾，因此，由所有
结尾的最长递增序列的长度，构成了问题的解空间。因此，再引入符号L，来描述问题的解空间：
-
表示以
显然，为该递增子序列的最大值，
就是问题的最优解。
求解，就要得到所有的
。求解
这一问题，包含了求解从
到
的所有子问题，从而满足最优子结构性质。
递归方程如下：
转换成代码，思路就是遍历所有，选择满足
的最大的
，则
，如果
比所有
都要小，则
。
完整代码
Leetcode上面有这个问题，可以上去检验一下：
class Solution {
public:
int max(const int &a, const int &b)
{
return a>b?a:b;
}
int lengthOfLIS(vector<int> &nums)
{
int n = nums.size();
int res = 1;
if(nums.size() == 0) return 0;
int *l = new int[n];
l[0] = 1;
for(int i = 1; i < n; i++) //填充L
{
int maxval = 1;
for(int j = 0; j < i; j++) //遍历所有的A
{
if(nums[i] > nums[j])
{
maxval = max(maxval, l[j]+1);
}
l[i] = maxval;
}
}
for(int i = 0; i < n; i++)
{
if(l[i]>res)
{
res = l[i];
}
}
return res;
}
};
