POJ （dp最长上升子序列问题）

题意：一组数求最长上升子序列。

思路：设置dp[i]的状态是以a[i]为结尾的最长子序列。那么可以想到只要弄清楚小于i的数字或者字符就行了。

#include<iostream>
#include<cstdio>

using namespace std;

#define Max 1010

int dp[Max];
int a[Max];
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n) != EOF){
        int ans = 0;
        for(int i = 0;i < n; i++)
            scanf("%d",&a[i]);
        for(int i = 0;i < n; i++){
            dp[i] = 1;
            for(int j = 0;j < i; j++){
                if(a[j] < a[i])
                    dp[i] = max(dp[i],dp[j]+1);
            }
            ans = max(dp[i],ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}