锐客网

  1. 首页 > it技术 > >

求最长上升子序列的最大长度


【求最长上升子序列的最大长度】问题描述
一个数的序列 bi，当 b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一
个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里 1 <= i1 < i2 < ... <
iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。
这些子序列中最长的长度是 4，比如子序列(1, 3, 5, 8).
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入数据
输入的第一行是序列的长度 N (1 <= N <= 1000)。第二行给出序列中的 N个整数，这些
整数的取值范围都在 0到 10000。
输出要求
最长上升子序列的长度。
输入样例
7
1 7 3 5 9 4 8
输出样例
4

#include #include int arry[1001]; int len[1001]; int main() { int i, j; int n, maxLen; scanf("%d", &n); for( i = 1; i <= n; i++ ) { scanf("%d", &arry[i]); } len[1] = 1; for( i = 2; i <= n; i++ ) { maxLen = 0; for( j = 1; j < i; j++ ) { if( len[j] > maxLen && arry[j] < arry[i] ) { /* *如果i位置的权值大于j位置的权值， *且j处得长度大于j以前的长度，i才能加入到j的后面 */ maxLen = len[j]; } } len[i] = maxLen+1; }maxLen = 0; for( i = 1; i <= n; i++ ) { if( len[i] > maxLen )maxLen = len[i]; } printf("%d\n", maxLen); return 0; }

    推荐阅读


    上一篇：Linux中${}、$()、$(())的功能

    下一篇：线性表（1.什么是线性表）