sdut 1299 最长上升子序列

最长上升子序列

PRoblem Description

Input

Output

Example Input

71 7 3 5 9 4 8
Example Output
4
Hint
Author
Northeastern Europe 2002 做以前我们首先应该明白一些东西。1、以某个数字为结尾的上升序列长度的最小值是1.（即只是包含它本身）2、假设数组x的长度为N，我们只要求出从以x[0]为结尾的最长子序列长度到以x[n-1]为结尾的最长子序列的长度，就可以知道这个数字的最长子序列长度了。
#include<stdio.h>#include<string.h>int main(){	int m[1008], save[1008];	int n;	scanf("%d", &n);	for (int i = 0; i < n; i++)	{		scanf("%d", &save[i]);		m[i] = 1;	}	for (int i = 1; i < n; i++)	{		int max = 0;		for (int c = 0; c < i; c++)		{			if (save[i]>save[c] && m[c]>max)				max = m[c];		}		m[i] = max + 1;	}	int max = 0;	for (int i = 0; i < n;i++)	if (m[i]>max)		max = m[i];	printf("%d/n", max);}