1016 最大上升子序列和

柔光的暖阳◎ 2022-09-11 13:13 171阅读 0赞

**1. 问题描述：**

一个数的序列 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)等等。这些子序列中和最大为18，为子序列(1,3,5,9)的和。你的任务，就是对于给定的序列，求出最大上升子序列和。  
注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

**输入格式**

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

**输出格式**

输出一个整数，表示最大上升子序列和。

**数据范围**

1 ≤ N ≤ 1000

**输入样例：**

7  
1 7 3 5 9 4 8

**输出样例：**

18  
来源：[https://www.acwing.com/problem/content/1018/][https_www.acwing.com_problem_content_1018]

**2. 思路分析：**

这道题目类似于**最长上升子序列**问题，也是属于动态规划的题目，我们也是可以分为两个步骤处理：① 状态表示 ② 状态计算；我们可以定义一个一维数组dp，其中dp\[i\]表示以a\[i\]结尾的最大上升子序列和；怎么样进行状态的计算呢？状态的计算对应集合的划分，类似于最长上升子序列问题我们可以按照倒数第二个数字划分为i类（上一个数可能大于当前的a\[i\]所以有可能某些类是不合法的），可以得到对应的状态转移方程为dp\[i\] = max(dp\[i\]，dp\[j\] + a\[i\])。

**3. 代码如下：**

if __name__ == '__main__':
        n = int(input())
        a = list(map(int, input().split()))
        dp = [0] * n
        res = 0
        for i in range(n):
            dp[i] = a[i]
            for j in range(i):
                if a[i] > a[j]:
                    dp[i] = max(dp[i], dp[j] + a[i])
            res = max(res, dp[i])
        print(res)

[https_www.acwing.com_problem_content_1018]: https://www.acwing.com/problem/content/1018/