C语言动态规划&背包最长上升子序列

蔚落 2022-06-01 08:40 269阅读 0赞

### 最长上升子序列 ###

Time Limit: 3000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2, ..., a N)，我们可以得到一些上升的子序列(a i1, a i2, ..., a iK)，这里1<= i 1 < i 2< ... < i K <= 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 ####

7
    1 7 3 5 9 4 8

#### Example Output ####

#include <stdio.h>
    int main()
    {
        int n, i, k;
        scanf("%d", &n);
        int a[1010], maxlen[1010];
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
        }
        maxlen[1] = 1;
        for(k = 2; k <= n; k++)
        {
            int m = 0;
            for(i = 1; i < k; i++)
            {
                if(a[k] > a[i] && m < maxlen[i])
                    m = maxlen[i];
                    maxlen[k] = m + 1;
            }
        }
        int max = maxlen[1];
        for(i = 2; i <= n; i++)
        {
            if(max < maxlen[i])
                max = maxlen[i];
        }
        printf("%d\n", max);
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2381/pid/1299.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2381/pid/1299.html