problem_longestserial.cpp

ACM中南大学找最大合法序列的算法

//Problem : 最长合法序列 
#include <stdio.h>
#include <string.h>
int a[1000],Len[1000],n;
int main(){
    int maxLen,i,j,k,p;
    scanf("%d",&n);
    for (i=0;i<n;i++){
        scanf("%d",&k);
        for (j=0;j<k;j++) scanf("%d",&a[j]);
        memset(Len,0,sizeof(Len));
        for (j=0;j<k;j++) Len[j]=1;
        for (j=1;j<k;j++){
            for (p=0;p<j;p++){
                if (a[j]>=a[p] && Len[j]<Len[p]+1) Len[j]=Len[p]+1;
            }    
        }    
        maxLen=0;
        for (j=0;j<k;j++){
            if (Len[j]>maxLen) maxLen=Len[j];
        }    
        printf("%d",maxLen);
        if (i<n-1) printf("\n");        
    }    
    
    return 0;
}     

/*
2
12 13 45 23 53 23 88 123 3 125 10 87 89
6 1 4 2 5 2 3
*/