POJ-2533-Longest Ordered Subsequence.txt

/**
 *POj-2533-Longest Ordered Subsequence
 *xuchen
 *2015-10-13
**/
#include "stdio.h"
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 10005;
int dp[N];
int a[N];

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d", &a[i]);

	int tmpMax;
	dp[0] = 1;
	for(int i=1; i<n; i++)
	{
		tmpMax = 1;
		for(int j=0; j<i; j++)
		{
			if(a[i]>a[j])
			{
				tmpMax = max(tmpMax, dp[j]+1);
			}
		}
		dp[i] = tmpMax;
	}

	int ans=0;
	for(int i=0; i<n; i++)
	{
		ans = max(ans, dp[i]);
	}
	printf("%d\n", ans);

	return 0;
}