7-1-1 最大子列和问题 分数 14 作者 DS课程组 单位 浙江大学

最大子列和问题是动态规划的一个经典问题，目标是找到给定数组中连续子数组的最大和。给定一个整数数组 nums，我们需要找到一个连续子数组（可以为空），使得这个子数组的所有元素之和最大。

这个问题可以通过创建一个辅助数组来解决，每个元素存储以当前位置结束的最长递增子序列的和。算法的主要思路是遍历整个数组，对于每个元素，有三种情况：

1. 如果当前元素比前一个元素小，则它的最大子序和就是它本身，因为它需要从头开始构造一个新的子序列。
2. 如果当前元素大于或等于前一个元素，那么可以保留当前元素，或者从前一个元素开始加上当前元素，取两者中的较大值，作为新子序列的和。
3. 更新全局最大子列和，如果当前元素加入后的新子序列和更大。

以下是伪代码和关键步骤描述：

def maxSubArray(nums):
    # 初始化辅助数组，first[i]表示以nums[i]结尾的最长递增子序列的起始索引
    first = [0] * len(nums)
    # 初始化辅助数组，max_sum[i]表示以nums[i]结尾的最长递增子序列的和
    max_sum = [nums[0]] + [-float('inf')] * (len(nums) - 1)

    # 遍历数组
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            # 当前元素比前一个大，直接添加
            max_sum[i] = nums[i]
            # 更新最长递增子序列的起始索引
            first[i] = i
        else:
            # 否则，寻找左边界，使得nums[i] + 左边界之前的子序列和最大
            left = first[i - 1]
            # 如果nums[left]加起来比nums[i]大，说明应该从left开始
            max_sum[i] = max(max_sum[i], nums[i] + max_sum[left])
            # 更新起始索引，选择能提供更大和的左边界
            first[i] = left + 1

    # 返回全局最大子列和
    return max_sum[-1]

# 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 输出：6 （子数组[4,-1,2,1]）

相关问题--
1. 除了动态规划，还有哪些其他解法可以解决最大子列和问题？
2. 这种方法为什么能在O(n)时间内解决问题？
3. 对于负数的数组，这种解决方案还能正常工作吗？为什么？