LIS的第二次理解

给定一组数列：a1,a2,...an;
求该数列的最长的递增长度？
解法：动态规划
状态转移方程：dp[i]=max(dp[i],dp[j]+1)
code：

int dp[maxn],a[maxn],m;
cin>>n;
dp[1]=1;
for(int i=1;i<=n;++i)
{
    cin>>a[i];
    for(int j=i-1;j>0;--j)
    {
         if(a[j]<a[i])    {dp[i]=max(dp[i],dp[j]+1);}
    }
    if(dp[i]==0)   dp[i]=1;
    m=max(m,dp[i]);
}

解释状态转移方程：
1.顺序问题：有两个顺序：
一、输入数列的顺序，1~n
二、递推的顺序：n_{1(也可以是1}n，这不影响，因为我们的递推每次都取最大值)