Input

10 9 2 5 3 7 101 18

Output

4 （因为2,3,7,101是最长的递增子序列）

解题思路

该问题满足最优子结构性质，因此可以使用动态规划求解。

定义如下符号：

$n$ 表示问题序列的总长度。
$A[1:i]$ 表示下标从1到i的一个序列，特别地， $A[1:n]$ 表示下标从1开始，长度为n的一个序列，也就是问题的输入。
$A_i$ 表示 $A[1:n]$ 中的第 $i$ 个元素。

由于问题的最优解必然对应某个子序列，而这个子序列又必然由某个 $A_i$ 结尾，因此，由所有 $A_i$ 结尾的最长递增序列的长度，构成了问题的解空间。因此，再引入符号L，来描述问题的解空间：

$L_i$ 表示以 $A_i$ 结尾的最长递增子序列的长度。

显然， $A_i$ 为该递增子序列的最大值， $\max (L_i)$ 就是问题的最优解。

求解 $\max (L_i)$ ，就要得到所有的 $L_i$ 。求解 $L_i$ 这一问题，包含了求解从 $L_{1}$ 到 $L_{i-1}$ 的所有子问题，从而满足最优子结构性质。

递归方程如下：

$L_k=\begin{cases} 1, & {\forall} i\in [1,k), A_k\leqslant A_i\\ \max(L_i)+1|i\in [1,k), A_k> A_i , & \exists i\in [1,k), A_k> A_i \end{cases}$

转换成代码，思路就是遍历所有 $A_i$ ，选择满足 $A_k>A_i$ 的最大的 $L_i$ ，则 $L_k=L_i+1$ ，如果 $A_k$ 比所有 $A_i$ 都要小，则 $L_k=1$ 。

完整代码

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;
}

};

参考资料：https://www.zhihu.com/question/23995189