longgestundecreaselist.cpp

求出一个序列的最长升序列,使用了动态规划的方法

#include <iostream>
using namespace std;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t,i,n,*a,j,k,max;
    int *num;
    cin>>t;
    i=0;
    while(i<t)
    {
              
              cin>>n;
              a=new int[n+1];              //a[i]用于表示以第i个数为尾数的最长升序列的长度 
              num=new int[n+1];
             
              num[0]=0;
              a[0]=0;
              for(j=1;j<=n;j++)
              {
              cin>>num[j];
              a[j]=0;
              }
              
              for(j=1;j<=n;j++)
              {
                   max=0;
                   for(k=1;k<j;k++)
                   {
                         if(a[k]>max&&num[j]>num[k])           
                         max=a[k];                
                                    }
                         a[j]=max+1;
                         //cout<<"a[j]="<<a[j]<<endl;
                               }
                               
              max=0;                             //整个数组a中，a[n]的值并不一定是最大的 
              for(j=1;j<=n;j++)
              {
                if(a[j]>max)
                max=a[j];               
                               }
              cout<<max<<endl;       
              i++;                 
              
              }
              system("pause");
              return 0;
    }
/*最长升序列的状态转移方程为a[i]=max{a[j]:j<i&&num[j]<num[i]}*/