最大子数组和

标签: 数组 分治 动态规划

难度: Medium

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

Submission

运行时间: 52 ms

内存: 15.3 MB

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        s = 0
        for num in nums:
            if s < 0:
                s = num
            else:
                s += num
            max_sum = max(max_sum, s)
        return max_sum

Explain

这个题解使用了动态规划的思想。通过遍历数组,对于每个元素,判断将其加入当前子数组是否会使当前子数组的和增大。如果当前子数组的和小于0,那么加上当前元素会使子数组的和变小,因此将当前子数组的和重置为当前元素。否则,将当前元素加入子数组。同时,更新最大子数组和。最终返回遍历过程中得到的最大子数组和。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')  # 初始化最大子数组和为负无穷
        s = 0  # 初始化当前子数组的和为0
        for num in nums:  # 遍历数组中的每个元素
            if s < 0:  # 如果当前子数组的和小于0
                s = num  # 将当前子数组的和重置为当前元素
            else:
                s += num  # 否则,将当前元素加入子数组
            max_sum = max(max_sum, s)  # 更新最大子数组和
        return max_sum  # 返回最大子数组和

Explore

在动态规划中,如果当前子数组的和小于0,意味着它对增加未来元素的总和没有贡献,反而会减少总和。因此,最优的选择是放弃当前的子数组和,从新的元素重新开始计算子数组的和。这样可以确保子数组的最大可能和不会被一个负的子数组和所拖累。

初始化`max_sum`为负无穷大是为了确保在遍历数组的过程中,任何一个元素的值都能被考虑进最大子数组和中,即使所有元素都是负数。这种初始化方法保证了`max_sum`能够正确地更新为数组中的最大值。另一种可能的初始化方式是将`max_sum`初始化为数组中的第一个元素,但这需要额外的逻辑来确保数组不为空。

是的,题解中的动态规划解法已经考虑了所有边界情况。即使数组中所有元素都是负数,通过初始化`max_sum`为负无穷并在每个元素上更新它,可以保证找到最大的子数组和,即便这个和依然是负数。对于只包含一个元素的数组,算法会将这个单一元素作为子数组,因此也能得到正确结果。

动态规划的方法在处理大数组(如长度接近10^5)时仍然有效,因为它的时间复杂度是O(n),这意味着算法对每个元素只进行一次操作。尽管如此,对于非常大的数组,还需要考虑内存使用和可能的整数溢出问题。在实际应用中,可能需要额外的逻辑来处理如整数溢出等边界和异常情况。