摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:DP(LIS+LDS)

/***********************************************************/

#include<stdio.h>  
#include<stdlib.h>  
 
int DP(int M,int num[])     
{     
 int a,b;  
 int LIS[2001]={0};  
 int LDS[2001]={0};  
   
 for(a=0;a<M;a++) LIS[a]=LDS[a]=1;  
   
 for(a=0;a<M;a++)  
    for(b=0;b<a;b++)  
       {  
          if(num[b]<num[a]&&LDS[a]<LDS[b]+1)  
            LDS[a]=LDS[b]+1;  
          if(num[b]>num[a]&&LIS[a]<LIS[b]+1)  
            LIS[a]=LIS[b]+1;    
       }  
    int max=0;     
    for(a=0;a<M;a++)     
       if(LDS[a]+LIS[a]-1>max) max=LDS[a]+LIS[a]-1;  
 
    return max;  
}    
main()  
{   
 int n,m,a,b,c;  
 scanf("%d",&n);   
 while(n--)  
  {  
   int num[2001]={0};  
   scanf("%d",&m);   
   for(a=m-1;a>=0;a--)  
    scanf("%d",&num[a]);   
     printf("%d\n",DP(m,num));   
  }     
 return 0;  
}