上升子序列

ゞ浴缸里的玫瑰 2022-05-16 01:45 144阅读 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  
对于每组测试数据，输出其最大上升子序列的和。  
Sample Input  
7  
1 7 3 5 9 4 8  
Sample Output  
18

#include <stdio.h>
    #include <stdlib.h>
    int main()
    {
        int n,i,j;
        int a[1001],b[1001];
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0;i<=n-1;i++)
            {
                scanf("%d",&a[i]);
            }
            b[0]=a[0];
            for(i=1;i<=n-1;i++)
            {
                int sum=0;
                for(j=0;j<i;j++)
                {
                    if(a[i]>a[j]&&sum<b[j])
                    {
                        sum=b[j];
                    }
                    b[i]=sum+a[i];
                }
    
            }
            int max=b[0];
            for(i=1;i<=n-1;i++)
            {
                if(b[i]>max)
                {
                    max=b[i];
                }
            }
            printf("%d\n",max);
        }
        return 0;
    }

与最长上升子序列如出一辙，详细见最长上升子序列，只不过改成加和的形式。