线性动态规划：最长递增子序列的变种——带权值的最长递增子序列（Maximum Sum Increasing Subsequence）
字数 2490 2025-11-21 12:40:38
线性动态规划：最长递增子序列的变种——带权值的最长递增子序列（Maximum Sum Increasing Subsequence）
题目描述
给定一个整数数组 nums，找到其中严格递增子序列的最大权值和。这里的"权值和"指的是子序列中所有元素的和。注意：子序列不要求连续，但必须保持原数组中的相对顺序，并且严格递增（即不能有相等元素）。
例如：
- 输入：
nums = [1, 101, 2, 3, 100, 4, 5] - 输出：
106（对应子序列[1, 2, 3, 100]，和为1 + 2 + 3 + 100 = 106）
解题思路
这个问题是经典最长递增子序列（LIS）问题的变种。在标准LIS中，我们只关心子序列的长度；而在这里，我们需要在保持递增性质的前提下，最大化子序列的权值和。
动态规划状态定义：
- 定义
dp[i]表示以第i个元素结尾的递增子序列的最大权值和。
状态转移方程：
- 对于每个位置
i，我们需要检查所有j < i：- 如果
nums[j] < nums[i]，说明可以将nums[i]接在以nums[j]结尾的递增子序列后面，形成一个新的递增子序列。 - 此时，以
i结尾的递增子序列的权值和为dp[j] + nums[i]。
- 如果
- 因此，状态转移方程为：
\[ dp[i] = \max(dp[i], dp[j] + nums[i]) \quad \text{对于所有 } j < i \text{ 且 } nums[j] < nums[i] \]
- 如果没有任何
j满足条件，那么dp[i] = nums[i]（即子序列只包含nums[i]自身）。
初始化：
- 每个
dp[i]初始化为nums[i]，因为至少可以取自身作为一个子序列。
最终答案：
- 遍历所有
dp[i]，取最大值作为结果。
详细步骤
我们通过示例 nums = [1, 101, 2, 3, 100, 4, 5] 来逐步演示：
-
初始化 dp 数组：
dp = [1, 101, 2, 3, 100, 4, 5]
-
处理 i = 1（nums[1] = 101）：
- 检查 j = 0：
nums[0] = 1 < 101，可以接在后面。 dp[1] = max(101, dp[0] + 101) = max(101, 1 + 101) = 102- 更新
dp = [1, 102, 2, 3, 100, 4, 5]
- 检查 j = 0：
-
处理 i = 2（nums[2] = 2）：
- 检查 j = 0：
1 < 2，dp[2] = max(2, 1 + 2) = 3 - 检查 j = 1：
101 > 2，跳过。 - 更新
dp = [1, 102, 3, 3, 100, 4, 5]
- 检查 j = 0：
-
处理 i = 3（nums[3] = 3）：
- 检查 j = 0：
1 < 3，dp[3] = max(3, 1 + 3) = 4 - 检查 j = 1：
101 > 3，跳过。 - 检查 j = 2：
2 < 3，dp[3] = max(4, 3 + 3) = 6 - 更新
dp = [1, 102, 3, 6, 100, 4, 5]
- 检查 j = 0：
-
处理 i = 4（nums[4] = 100）：
- 检查 j = 0：
1 < 100，dp[4] = max(100, 1 + 100) = 101 - 检查 j = 1：
101 > 100，跳过。 - 检查 j = 2：
2 < 100，dp[4] = max(101, 3 + 100) = 103 - 检查 j = 3：
3 < 100，dp[4] = max(103, 6 + 100) = 106 - 更新
dp = [1, 102, 3, 6, 106, 4, 5]
- 检查 j = 0：
-
处理 i = 5（nums[5] = 4）：
- 检查 j = 0：
1 < 4，dp[5] = max(4, 1 + 4) = 5 - 检查 j = 1：
101 > 4，跳过。 - 检查 j = 2：
2 < 4，dp[5] = max(5, 3 + 4) = 7 - 检查 j = 3：
3 < 4，dp[5] = max(7, 6 + 4) = 10 - 检查 j = 4：
100 > 4，跳过。 - 更新
dp = [1, 102, 3, 6, 106, 10, 5]
- 检查 j = 0：
-
处理 i = 6（nums[6] = 5）：
- 检查 j = 0：
1 < 5，dp[6] = max(5, 1 + 5) = 6 - 检查 j = 1：
101 > 5，跳过。 - 检查 j = 2：
2 < 5，dp[6] = max(6, 3 + 5) = 8 - 检查 j = 3：
3 < 5，dp[6] = max(8, 6 + 5) = 11 - 检查 j = 4：
100 > 5，跳过。 - 检查 j = 5：
4 < 5，dp[6] = max(11, 10 + 5) = 15 - 更新
dp = [1, 102, 3, 6, 106, 10, 15]
- 检查 j = 0：
-
求最大值：
max(dp) = max(1, 102, 3, 6, 106, 10, 15) = 106
最终结果为 106，对应子序列 [1, 2, 3, 100]。
复杂度分析
- 时间复杂度：O(n²)，其中 n 是数组长度。对于每个元素，需要检查所有之前的元素。
- 空间复杂度：O(n)，用于存储 dp 数组。
关键点总结
- 状态定义：
dp[i]表示以nums[i]结尾的递增子序列的最大权值和。 - 状态转移：通过遍历之前的所有元素，找到可以接在后面的递增子序列，并更新最大权值和。
- 初始化：每个位置初始化为自身值。
- 结果提取：最终结果是
dp数组中的最大值。
这个算法在标准LIS的基础上增加了权值和的考虑，适用于需要最大化子序列和而不仅仅是长度的场景。