线性动态规划：最长递增子序列的变种——带权值的最长递增子序列（Maximum Sum Increasing Subsequence）

字数 1554 2025-11-11 13:23:48

线性动态规划：最长递增子序列的变种——带权值的最长递增子序列（Maximum Sum Increasing Subsequence）

题目描述
给定一个整数数组 nums，找到其所有递增子序列中，子序列元素和最大的那个，返回该最大和。
注意：子序列不要求连续，但必须严格递增（即不能有相等元素）。
示例：
输入：nums = [1, 3, 2, 4, 5]
输出：15（因为最长递增子序列 [1, 3, 4, 5] 的和为 13，但带权值的最优解是 [1, 2, 4, 5] 的和为 12？这里需要修正：实际上应计算所有递增子序列的最大和。对于示例，最大和递增子序列是 [1, 3, 4, 5] 和为 13，但若数组为 [1, 101, 2, 3, 100]，最大和递增子序列是 [1, 2, 3, 100] 和为 106，而不是最长递增子序列 [1, 101] 的和 102）。

解题过程

问题分析
本题是经典最长递增子序列（LIS）的变种，不同之处在于：
- LIS 要求子序列长度最大化，而本题要求子序列的元素和最大化。
- 递增子序列需满足严格递增条件（即 i < j 且 nums[i] < nums[j]）。
状态定义
定义 dp[i] 表示以 nums[i] 结尾的递增子序列的最大和。
注意：dp[i] 必须包含 nums[i] 自身，因为子序列以 nums[i] 结尾。
状态转移方程
对于每个位置 i，需要检查所有 j < i：
- 如果 nums[j] < nums[i]，说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面，形成更长的递增子序列。
- 此时，dp[i] 可能更新为 dp[j] + nums[i]。
  因此，状态转移方程为：
```
dp[i] = max(nums[i], max{ dp[j] + nums[i] for all j < i and nums[j] < nums[i] })
```
其中 max(nums[i]) 表示单独以 nums[i] 作为一个子序列的情况。
初始化
每个元素至少可以单独作为子序列，因此初始化 dp[i] = nums[i]。
计算顺序与结果提取
- 按 i 从 0 到 n-1 顺序计算 dp[i]。
- 最终结果是所有 dp[i] 中的最大值，因为最大和递增子序列可能以任意位置结尾。
示例演示
以 nums = [1, 101, 2, 3, 100] 为例：
- dp[0] = 1（子序列 [1]）
- dp[1] = max(101, 1 + 101) = 102（子序列 [1, 101]）
- dp[2] = max(2, 1 + 2) = 3（子序列 [1, 2]）
- dp[3] = max(3, 1 + 3, 3 + 3?) 注意：只能接在满足 nums[j] < nums[3] 的 j 后，即 j=0 和 j=2，所以 dp[3] = max(3, 1+3, 3+3?) 修正：dp[3] = max(3, dp[0]+3=4, dp[2]+3=6) = 6（子序列 [1, 2, 3]）
- dp[4] = max(100, dp[0]+100=101, dp[2]+100=103, dp[3]+100=106) = 106（子序列 [1, 2, 3, 100]）
  最终结果 max(dp) = 106。
复杂度分析
- 时间复杂度：O(n²)，因每个 i 需遍历所有 j < i。
- 空间复杂度：O(n)，用于存储 dp 数组。

关键点

与经典 LIS 的区别在于，状态值从“长度”变为“和”，但转移逻辑一致。
需注意初始化时 dp[i] 至少为 nums[i]，保证单独成序列的情况。

线性动态规划：最长递增子序列的变种——带权值的最长递增子序列（Maximum Sum Increasing Subsequence）题目描述给定一个整数数组 nums ，找到其所有递增子序列中，子序列元素和最大的那个，返回该最大和。注意：子序列不要求连续，但必须严格递增（即不能有相等元素）。示例：输入： nums = [1, 3, 2, 4, 5] 输出： 15 （因为最长递增子序列 [1, 3, 4, 5] 的和为 13，但带权值的最优解是 [1, 2, 4, 5] 的和为 12？这里需要修正：实际上应计算所有递增子序列的最大和。对于示例，最大和递增子序列是 [1, 3, 4, 5] 和为 13，但若数组为 [1, 101, 2, 3, 100] ，最大和递增子序列是 [1, 2, 3, 100] 和为 106，而不是最长递增子序列 [1, 101] 的和 102）。解题过程问题分析本题是经典最长递增子序列（LIS）的变种，不同之处在于： LIS 要求子序列长度最大化，而本题要求子序列的元素和最大化。递增子序列需满足严格递增条件（即 i < j 且 nums[i] < nums[j] ）。状态定义定义 dp[i] 表示以 nums[i] 结尾的递增子序列的最大和。注意： dp[i] 必须包含 nums[i] 自身，因为子序列以 nums[i] 结尾。状态转移方程对于每个位置 i ，需要检查所有 j < i ：如果 nums[j] < nums[i] ，说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面，形成更长的递增子序列。此时， dp[i] 可能更新为 dp[j] + nums[i] 。因此，状态转移方程为：其中 max(nums[i]) 表示单独以 nums[i] 作为一个子序列的情况。初始化每个元素至少可以单独作为子序列，因此初始化 dp[i] = nums[i] 。计算顺序与结果提取按 i 从 0 到 n-1 顺序计算 dp[i] 。最终结果是所有 dp[i] 中的最大值，因为最大和递增子序列可能以任意位置结尾。示例演示以 nums = [1, 101, 2, 3, 100] 为例： dp[0] = 1 （子序列 [1] ） dp[1] = max(101, 1 + 101) = 102 （子序列 [1, 101] ） dp[2] = max(2, 1 + 2) = 3 （子序列 [1, 2] ） dp[3] = max(3, 1 + 3, 3 + 3?) 注意：只能接在满足 nums[j] < nums[3] 的 j 后，即 j=0 和 j=2，所以 dp[3] = max(3, 1+3, 3+3?) 修正： dp[3] = max(3, dp[0]+3=4, dp[2]+3=6) = 6 （子序列 [1, 2, 3] ） dp[4] = max(100, dp[0]+100=101, dp[2]+100=103, dp[3]+100=106) = 106 （子序列 [1, 2, 3, 100] ）最终结果 max(dp) = 106 。复杂度分析时间复杂度：O(n²)，因每个 i 需遍历所有 j < i 。空间复杂度：O(n)，用于存储 dp 数组。关键点与经典 LIS 的区别在于，状态值从“长度”变为“和”，但转移逻辑一致。需注意初始化时 dp[i] 至少为 nums[i] ，保证单独成序列的情况。