2640: 最长有序的子序列问题
金币值：3
定数：10
时间限制：1.000 s
内存限制：128 M
正确：3
提交：3
正确率：100.00% 命题人：
题目描述
在一个长度为n的无序整数序列中查找最长的有序子序列的长度。
测试代码 复制
#include "stdio.h"
void f(int count[],int a[],int n)
{
}
int main(void)
{
int i;
int a[101];
int count[101];
int n;
scanf("%d", &n);
for ( i = 1; i <= n; i++ )
{
scanf("%d", &a[i]);
}
f(count,a,n);
int max = count[1];
for ( i = 2; i <= n; i++ )
{
if ( count[i] > max ) max=count[i];
}
printf("%d\n", max);
return 0;
}输入格式
第1行输入1个正整数n的值。
第2行输入n个无序的整数序列。
输出格式
最长的有序子序列的长度。
输入样例 复制
6
5 2 3 4 1 6输出样例 复制
3提示
可以用动态规划实现。样例中的最长的有序子序列是2 3 4，长度为3。根据后一个元素与前一个元素的大小决定长度是增1还是从1开始重新计数。