上升子序列

骑猪看日落 2022-07-13 01:56 132阅读 0赞

#### 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\}等等。这些子序列中序列和最大的是子序列\{1, 3, 5, 9\}，它的所有元素的和为18。

对于给定的一个序列，求出它的最大的上升子序列的和。

注意：最长的上升子序列的和不一定是最大的哦。

#### Input ####

输入包含多组测试数据，对于每组测试数据：

输入数据的第一行为序列的长度 n(1 ≤ n ≤ 1000)，

第二行为ｎ个非负整数 b1，b2，...，bn(0 ≤ bi ≤ 1000)。

#### Output ####

对于每组测试数据，输出其最大上升子序列的和。

#### Example Input ####

7
    1 7 3 5 9 4 8

#### Example Output ####

#include<stdio.h>
    int main()
    {
        int n;
        int i,j,k,m;
        int a[1000]={0};
        int max[1000]={0};
        while(scanf("%d",&n)!=EOF)
        {
            memset(max,0,sizeof(max));
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            max[0]=a[0];
            for(i=1;i<n;i++)
            {
                k=0;
                for(j=0;j<n;j++)
                {
                    if(a[i]>a[j]&&max[j]>k)
                    {
                        k=max[j];
                    }
                }
                max[i]=k+a[i];
            }
            m=max[0];
            for(i=0;i<n;i++)
            {
                if(max[i]>m)
                    m=max[i];
            }
            printf("%d\n",m);
        }
        return 0;
    }