最长上升子序列之基础 - JAVA

Font Size:Aa Aa Aa

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

代码如下：

#include

#define maxn 1005 int a[maxn]; int dp[maxn]; int max(int x,inty) { returnx>y x:y; } int main() { intt,n; scanf("%d",&t); while(t--) { scanf("%d",&n); inti,j; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=0;i<=n;i++) dp[i]=1; intans=0; for(i=1;i<=n;i++) { for

(j=1;j
       
        
       if
       (a[j]
         
          
         dp[i]=max(dp[i],dp[j]+1); 
          
         ans=max(dp[i],ans); 
          
         } 
          
         printf
         (
         "%d\n"
         ,ans); 
          
         } 
          
         return
         0;  
         }