求最长不下降序列(动规)

求最长不下降序列

问题描述：

       设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j)  (i<>j)，若存在i1<i2<i3< … < ie 且有b(i1)<b(i2)< … <b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。

       例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63长度为8的不下降序列。

输入：13 7 9 16 38 24 37 18 44 19 21 22 63 15

输出：   8

　　　　7  9  16  18  19  21  22  63

#include<iostream>
using namespace std;
int pre[1001];
int f[1001];
int num[1001];
int h,d,c,w=1;
int maxn=0;
void print (int a)
{
    if(!pre[a])return ;
    print(pre[a]);
    cout<<num[a]<<" ";
}
int main() 
{
    while(cin>>num[++h]);
    for(int i=1;i<=h;++i)
    {
        f[i]=1;
        maxn=0;
        for(int j=1;j<i;++j)
        {
            if(f[j]>maxn&&num[j]<num[i]) 
            {
                maxn=f[j];
                f[i]=f[j]+1;
                c=j;
            }
        }
        pre[i]=c;
        if(f[i]>d)
        {
            d=f[i];
            w=i;
        }
    }
    cout<<d<<endl;
    print(w);
    return 0;
}