Font Size:

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

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

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

171  7  3  5  9  4  8

4

代码例如以下：

#include <stdio.h>

#define maxn 1005

int

a[maxn];

int

dp[maxn];

int

max(

int

x,

int

y)

{

    

return

x>y?x:y;

}

int

main()

{

    

int

t,n;

      

    

scanf

(

"%d"

,&t);

    

while

(t--)

    

{

        

scanf

(

"%d"

,&n);

        

int

i,j;

        

for

(i=1;i<=n;i++)

            

scanf

(

"%d"

,&a[i]);

        

for

(i=0;i<=n;i++)

            

dp[i]=1;

        

int

ans=0;

        

for

(i=1;i<=n;i++)

        

{

            

for

(j=1;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;

}

版权声明：本文博主原创文章，博客，未经同意不得转载。