最长上升子序列之基础

swustpoweroj 1180     
Time Limit:1000MS Memory Limit:65536KB

动态规划（DP）

Description

给出一个由n个数组成的序列x[1..n]，找出它的最长单调上升子序列的长度。
即找出最大的长度m和a1,a2……,am，使得 a1 < a2 < … … < am且 x[a1] < x[a2] < … … < x[am]。

Input

先输入一个整数t（t<=200），代表测试组数。
每组数据先输入一个N，代表有N个数（1<=N<=1000）.
输入N个正整数，a1，a2，a3.....an（0<=ai<=100000）.

Output

每组输出一个整数，代表最长的长度。

Sample input

1
7
1 7 3 5 9 4 8

Sample Output

4

完整代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10010],f[10010];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,x,i,j,m=-1;
        scanf("%d",&n);
        for(i=0;i<n;i++)
           f[i]=1;
        for(i=0;i<n;i++)
             scanf("%d",&a[i]);
        for(i=0;i<n;i++)
         {
             for(j=0;j<i;j++)
                if(a[j]<a[i])
                    f[i]=max(f[i],f[j]+1);
            m=max(m,f[i]);
         }
         printf("%d\n",m);
       }
    return 0;
}