POJ - 2533 Longest Ordered Subsequence解题报告（最长上升子序列）

#include<iostream>
#include<string.h>
#define N 1050

using namespace std;
int n;
int dp[N]={0};//以第i个数为结尾的最长上升子序列的长度为 pd[ i ]。 
int a[N]={0};

int main()
{
	while(cin>>n)
	{
		int best=0; 
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		for(int i=1;i<=n;i++)
		{
			int max=0;
			for(int j=1;j<i;j++)
			{
				if(a[i]>a[j]&&max<dp[j])
				{
					max=dp[j];
				}
			}
			dp[i]=max+1;
			if(best<dp[i])best=dp[i];
		}
		cout<<best<<endl;
		memset(dp,0,sizeof(dp));
	}
}