10001.c

Longest Ordered Subsequence,acm必备习题

#include <stdio.h>

#define MAX 1001

int n, num[MAX], dat[MAX];
// n 输入数组长度 
// num[] 存放数组 
// dat[] 

int main(int argc, char *argv[])
{
    int i, j, temp, t, maxnum;
    // i j tmp 临时量 
    // t 输入次数 
    // maxnum 记录最长上升序列长度 
    scanf("%d",&t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d", &num[i]);
            dat[i] = -1;
        }
        maxnum = 0; 
        for(i = 0; i < n; i++) {
            temp = 0;
            for(j = 0; j < i; j++) {
                if(num[j] < num[i] && temp < dat[j]) {
                    temp = dat[j];
                }
            }
            dat[i] = temp + 1;
            // find the longest ordered subsequence length
            if(dat[i] > maxnum)
                maxnum = dat[i];
        }
        printf("%d\n", maxnum);
    }
    return 0;
}