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
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;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4804242.html
