GroupBlog

Longest Ordered Subsequence

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 32183		Accepted: 14088

Description

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence ( a₁, a₂, ..., a_N) be any sequence ( a_i₁, a_i₂, ..., a_{i_K}), where 1 <= i₁ < i₂ < ... < i_K <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

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.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

题目大意

输入一个数字序列长度为N(1<=N<=1000),序列中的每个数字在0到10000之内，输出最长的上升序列长度.

样例:

7
1 7 3 5 9 4 8

其中1,3,5,9

   1,3,5,8

的长度均为4,因此没有比4更大的数字所以，最长得上串长度为4.（注意该串在原序列中可能不连续）.

我的思路:

如果记以i结尾的序列长度为d[i].

那么当a[j]>a[i]&&d[j]<d[i]+1时，d[j]=d[i]+1(j>i).

如果当将a[i]作为结尾添加到a[j]的后面（a[j]>a[i]时可以添加）如果长度大于他作为其他子序列的结尾时长度更长那么用

d[i]+1,替换d[j],原因是，要更新d[j]为以j位置结尾的子序列的最大长度.

初始时每个位置的数字都可以作为以自己开头以自己结尾的子序列，且长度为一.

问题的解是，以i结尾的子序列最大长度(1<i<=N)

原题链接:poj 2533 Longest Ordered Subsequence

Problem: 2533		User: 04123140
Memory: 408K		Time: 32MS
Language: GCC		Result: Accepted
#include <stdio.h>
#include <string.h>
#define size 2000
int str[size];
int d[size]={0};
int main (){
	int n,i,max;
	while(scanf("%d",&n)!=EOF){
		memset(d,0,sizeof(d)); 
		for(i=1;i<=n;i++){
			scanf("%d",&str[i]);
		}
		for(i=1;i<=n;i++){
			int j;
			d[i]=1;
			for(j=1;j<i;j++){
				if(str[i]>str[j]&&d[i]<=d[j]){
					d[i]=d[j]+1;
				}
			}
		}
		for(i=1,max=1;i<=n;i++){
			if(max<d[i]){
				max=d[i];
			}
		}
		printf("%d\n",max);
	}
	return 0;
}