dp[i] = max(nums[i], max_{j < i 且 nums[j] < nums[i]} { dp[j] + 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] ） 修正示例： 输入： nums = [1, 101, 2, 3, 100] 输出： 106 （子序列 [1, 2, 3, 100] 的和） 解题过程 这个问题是经典最长递增子序列（LIS）的变种，但目标从“最长长度”变为“最大和”。我们需要动态规划来记录以每个元素结尾的递增子序列的最大和。 步骤 1：定义状态 设 dp[i] 表示以第 i 个元素（ nums[i] ）结尾的递增子序列的最大和。 注意：子序列必须包含 nums[i] ，且严格递增。 步骤 2：状态转移方程 对于每个 i ，我们需要检查所有 j < i ： 如果 nums[j] < nums[i] ，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面，形成更长的递增子序列。 此时，以 nums[i] 结尾的最大和可能是 dp[j] + nums[i] 。 因此，状态转移方程为： 其中 nums[i] 表示单独以 nums[i] 作为一个子序列的情况。 步骤 3：初始化 每个元素至少可以单独构成子序列，所以初始时 dp[i] = nums[i] 。 步骤 4：计算顺序 从左到右遍历 i ，对于每个 i ，遍历所有 j < i 来更新 dp[i] 。 步骤 5：最终结果 结果不是 dp[n-1] ，因为最大和可能不以最后一个元素结尾。我们需要取 dp 数组中的最大值。 示例详解 以 nums = [1, 101, 2, 3, 100] 为例： i=0 ： dp[0] = 1 （子序列 [1] ） i=1 ：检查 j=0 （ 1 < 101 ）， dp[1] = max(101, 1+101) = 102 （子序列 [1,101] ） i=2 ：检查 j=0 （ 1 < 2 ）， dp[2] = max(2, 1+2) = 3 （子序列 [1,2] ） i=3 ：检查 j=0 （ 1 < 3 ）→ 1+3=4 ； j=2 （ 2 < 3 ）→ 3+3=6 ； dp[3] = max(3, 4, 6) = 6 （子序列 [1,2,3] ） i=4 ：检查 j=0 （ 1 < 100 ）→ 1+100=101 ； j=2 （ 2 < 100 ）→ 3+100=103 ； j=3 （ 3 < 100 ）→ 6+100=106 ； dp[4] = max(100, 101, 103, 106) = 106 （子序列 [1,2,3,100] ） 最终结果： max(dp) = max(1, 102, 3, 6, 106) = 106 复杂度分析 时间复杂度：O(n²)，需要两层循环。 空间复杂度：O(n)，用于存储 dp 数组。 优化提示 如果题目要求更优时间复杂度（如 O(n log n)），可以考虑类似 LIS 的贪心+二分查找方法，但需额外维护“最大和”信息，较为复杂。本题标准解法为 O(n²) 动态规划。