1285:最大上升子序列和
时间: 2023-12-06 13:45:20 浏览: 31
最大上升子序列和(Maximum Sum Increasing Subsequence)是一个经典的动态规划问题,它的解法可以用到“最长上升子序列”问题中的思想。
假设我们有一个序列 $a_1, a_2, \cdots, a_n$,我们要求出其中一个最大的上升子序列,并且计算其元素之和。设 $dp_i$ 表示以 $a_i$ 结尾的最大上升子序列和,则有:
$$
dp_i = \max_{j=1}^{i-1} \{dp_j + a_i\} \quad (a_j < a_i)
$$
其中 $a_j < a_i$ 表示只有当 $a_i$ 大于前面某个元素 $a_j$ 时,才能将 $a_i$ 加入到以 $a_j$ 结尾的上升子序列中。
最终的答案为 $\max_{i=1}^{n} \{dp_i\}$。
下面是一个 Python 实现的例子:
```python
def max_sum_increasing_subsequence(nums):
n = len(nums)
dp = nums.copy()
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + nums[i])
return max(dp)
# 示例
print(max_sum_increasing_subsequence([1, 101, 2, 3, 100, 4, 5])) # 输出 106(1 + 2 + 3 + 100)
```