最长合法序列 

Problem description
有k个整数A[1],A[2]...A[k],你需要从前往后选出若干个数,使得每一个后面的数都要大于或等于前面的

数.例如,对于系列1,4,2,5,2,3,选出1,2,2,3是合法的,但是选出4,2,3是不合法的.
请你编写程序对于一个已知系列,求出最长的合法系列的数的个数.

 
Input
第一行为n，表示n个测试序列; 第二行到第n+1行，每行开始第一个数为k,　k后面紧跟k个数A[1],A[2]

….A[k]。

 
Output
输出n行，每行输出一个整数，表示相应测试序列中最长的合法序列的数的个数。

 
Sample Input
2
12 13 45 23 53 23 88 123 3 125 10 87 89
6 1 4 2 5 2 3
 
Sample Output
6
4
 
Judge Tips
其中0

 
Problem Source
CSU 1st Contest
 
//我的代码

#include <stdio.h>
#include <stdlib.h>

struct Node{
 int i;
 int n;
};

int main(){
 int    nTest,i,j,k,n,m,max;
 struct Node *p;

 scanf("%d",&nTest);
 for(i = 0; i < nTest; i++){
  scanf("%d",&n);
  p = (struct Node*)malloc(sizeof(struct Node)*n);
  for(j = 0; j < n; j++){
   scanf("%d",&p[j].i);
   p[j].n = 1;
  }
  for(j = n - 1,max = 0; j >= 0; j--){
   for(k = j + 1,m = 0; k < n; k ++){
    if(p[j].i <= p[k].i && p[k].n > m)
     m = p[k].n;
   }
   p[j].n += m;
   if(p[j].n > max)
    max = p[j].n;
  }
  printf("%d\n",max);
  free(p);
 }
 return 0;
}

评论