最长子序列（不连续）

#include<bits/stdc++.h>
using namespace std;
//最长子序列
int dp[1005],a[1005];
int lis(int x)//共x个元素
{
    for(int i=0; i<x; i++)
    {
        dp[i]=1;//每一个元素的最初权值都为1
        for(int j=0; j<i; j++)
        {
            if(a[j]<a[i])
                dp[i]=max(dp[j]+1,dp[i]);//分布决策，把每一步的最优解保留下来
        }
    }
    int maxx=0;
    for(int i=0; i<x; i++)
    {
        if(maxx<dp[i])
            maxx=dp[i];
    }

    return maxx;
}
int main()
{
    int x;
    while(cin>>x&&x)
    {
        for(int i=0; i<x; i++)
            cin>>a[i];
        cout<<lis(x)<<endl;
    }

}
//分布决策把每一步的最优解保留下来