最长上升子序列

2019-11-10 21:10:21

字体：大中小

来源：转载

供稿：网友

PRoblem Description

一个数的序列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)。你的任务，就是对于给定的序列，求出最长上升子序列的长度。

Input

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

Output

最长上升子序列的长度。

Example Input

71 7 3 5 9 4 8Example Output
4Hint
Author
Northeastern Europe 2002
01 #include<stdio.h>
02 int main()
03 {
04     int a[1005], b[1005];
05     int i, n, max, j;
06     max = 0;
07     scanf("%d", &n);
08     for(i = 1; i <= n; i++)
09     {
10         scanf("%d", &a[i]);
11         b[i] = 0;
12     }
13     b[1] = 1;
14     for(i = 1; i <= n; i++)
15     {
16         b[i] = 1;
17         for(j = 1; j <= i; j++)
18         {
19             if(a[i] > a[j] && b[j] >= b[i])
20                 b[i] = b[j] + 1;
21         }
22     }
23     for(i = 1; i <= n; i++)
24         if(b[i] > max) max = b[i];
25     printf("%d/n", max);
26     return 0;
27 }