求最长非降子序列

2008-10-31 20:26

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int n = 10;
const int MAX = 1000000;
int main(void){
    int num[20];
    int f[20];
    int i,j;
    int from[20];
   
    for(i=0;i<20;i++) from[i] = -1;
    memset(f,0,sizeof(f));
    srand(time(NULL));
    for(i=0;i<n;i++) num[i] = rand()%100;
    num[n] = MAX;
    f[0] = 1;
   
    for(i=0;i<n;i++) cout<<num[i]<<" ";
    cout<<endl;
    system("pause");
    cout<<endl;
   
    for(i=1;i<=n;i++)
        for(j=0;j<i;j++)
            if(f[i]<f[j]+1&&num[i]>=num[j]){
                f[i] = f[j]+1;
                from[i] = j;
            }
   
    cout<<f[n]-1<<endl;
    i=n;j=0;
    while(j!=f[n]-1){
          cout<<num[from[i]]<<" ";
          i = from[i];
          j++;
    }
    cout<<endl;
   
    system("pause");
    return 0;
}