# 杰拉斯的博客

## [ACM_POJ_2533]Longest Ordered Subsequence

### Longest Ordered Subsequence （最长有序子序列）

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 21942 Accepted: 9441

#### Description

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

#### Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

#### Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

7
1 7 3 5 9 4 8

4

#### Source

POJ2533

a[n] = max({a[i] | 0 < i < n}) + 1

 I 0 1 2 3 4 5 6 7 8 Num[I] 1 4 7 2 5 8 3 6 9 F[I] 1 2 3 2 3 4 3 4 5

#include<stdio.h>
int main(){
int n, ans = 1;
scanf("%d", &n);
int *num = new int[n];
int *a = new int[n];
for(int i = 0; i < n; ++i){
scanf("%d", &num[i]);
int max = 0;
for(int j = 0; j < i; ++j){
if(num[j] < num[i] && a[j] > max){
max = a[j];
}
}
a[i] = max + 1;
if(a[i] > ans)
ans = a[i];
}
printf("%d", ans);
return 0;
}