首页 > 代码库 > 最长上升子序列之基础
最长上升子序列之基础
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)。代表測试组数。 Output每组输出一个整数。代表最长的长度。 Sample Input1 7 1 7 3 5 9 4 8 Sample Output4
代码例如以下:
#include <stdio.h> #define maxn 1005 int
a[maxn]; int
dp[maxn]; int
max( int x, int y)
{ return 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;
} |
最长上升子序列之基础
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。