Python实现最大和递增非连续子数组求解

这是个挺实用的问题——我们要找的不是最长的递增非连续子序列，而是总和最大的那个。拿你给的例子[5, 2, 4, 3, 7, 7]来说，最终输出[2, 4, 7]的总和是13，比其他可能的递增子序列（比如[5,7]总和12，[2,3,7]总和12）都要大。

我用动态规划来解决这个问题，不仅能算出最大和，还能还原出对应的子序列，步骤如下：

算法思路 #

1. 动态规划数组定义：
   • dp[i]：表示以nums[i]结尾的递增子序列的最大总和。
   • prev[i]：记录nums[i]在最大和子序列中的前一个元素的索引，用来后续回溯还原子序列。
2. 初始化：
   • dp数组初始化为原数组的拷贝，因为每个元素本身可以作为一个独立的子序列，总和就是它自己。
   • prev数组初始化为全-1，表示初始状态下每个元素都没有前驱。
3. 遍历更新：
   • 对于每个元素nums[i]，遍历它前面所有的元素nums[j]（j < i）。
   • 如果nums[j] < nums[i]，且dp[j] + nums[i]大于当前的dp[i]，说明把nums[i]接在以nums[j]结尾的子序列后面能得到更大的总和，就更新dp[i]和prev[i]。
4. 回溯还原子序列：
   • 找到dp数组中最大值对应的索引，这个索引就是最大和子序列的最后一个元素的位置。
   • 通过prev数组从后往前回溯，收集元素，最后反转得到正确顺序的子序列。

Python代码实现 #

def max_sum_increasing_subsequence(nums):
    if not nums:
        return []
    
    n = len(nums)
    dp = nums.copy()  # dp[i]表示以nums[i]结尾的最大和递增子序列的和
    prev = [-1] * n   # 记录前驱元素的索引
    
    for i in range(1, n):
        for j in range(i):
            # 如果nums[j]小于当前元素，且加上当前元素的和更大
            if nums[j] < nums[i] and dp[j] + nums[i] > dp[i]:
                dp[i] = dp[j] + nums[i]
                prev[i] = j
    
    # 找到最大和对应的最后一个元素的索引
    max_sum_idx = dp.index(max(dp))
    
    # 回溯构建子序列
    result = []
    current_idx = max_sum_idx
    while current_idx != -1:
        result.append(nums[current_idx])
        current_idx = prev[current_idx]
    
    # 反转得到递增顺序的子序列
    return result[::-1]

# 测试例子
nums = [5, 2, 4, 3, 7, 7]
print(max_sum_increasing_subsequence(nums))  # 输出: [2, 4, 7]

代码解释与验证 #

• 对于例子[5,2,4,3,7,7]：

  • 遍历到4（索引2）时，发现前面的2（索引1）小于它，dp[1]+4=2+4=6大于dp[2]初始值4，所以dp[2]更新为6，prev[2]设为1。
  • 遍历到第一个7（索引4）时，前面的4（索引2）的dp值是6，6+7=13，比其他候选（比如5+7=12，3+7=10）都大，所以dp[4]更新为13，prev[4]设为2。
  • 最后找到dp数组的最大值13对应的索引4，回溯得到7 ->4 ->2，反转后就是[2,4,7]，完全符合预期。

• 特殊情况测试：

  • 全递减数组[10,9,8,7]：输出[10]，因为单独选最大元素的和最大。
  • 单元素数组[5]：直接输出[5]。
  • 严格递增数组[1,2,3,4]：输出[1,2,3,4]，因为它的和就是最大的。

内容的提问来源于stack exchange，提问作者fiendfire28