环形子数组的最大和

标签: 队列 数组 分治 动态规划 单调队列

难度: Medium

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：

输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

提示：

  • n == nums.length
  • 1 <= n <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104​​​​​​​

Submission

运行时间: 61 ms

内存: 20.0 MB

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:

        
        n = len(nums)
        # 非循环内部
        whole0 = nums[0]
        curr = nums[0]
        
        for num in nums[1:n]:
            if curr < 0:
                curr = num
            else:
                curr += num
            if curr > whole0:
                whole0 = curr
        

        #循环外部（转成非循环内部的最小值）
        total = sum(nums)
        whole1 = total
        curr = float('inf')

        for num in nums[1:n-1]:
            if curr > 0:
                curr = num
            else:
                curr += num
            if (total-curr) > whole1:
                whole1 = total-curr
        
        if total > whole1:
            whole1 = total

        return whole0 if whole0>whole1 else whole1

Explain

此题解通过考虑两种情况来寻找最大子数组和：1. 子数组不包含环形的部分，即子数组完全位于数组的一个连续部分内。2. 子数组包含环形的部分，即子数组的一部分在数组的开头，另一部分在数组的结尾。对于第一种情况，直接使用Kadane算法找到最大子数组和。对于第二种情况，计算整个数组的总和，然后使用Kadane算法寻找非循环部分的最小子数组和，从总和中减去这个最小值，得到环形的最大子数组和。最后，比较这两种情况下的最大值，返回较大者。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:

        n = len(nums)
        # 使用Kadane算法找到非环形子数组的最大和
        whole0 = nums[0]
        curr = nums[0]
        for num in nums[1:n]:
            if curr < 0:
                curr = num
            else:
                curr += num
            if curr > whole0:
                whole0 = curr
        
        # 计算整个数组的总和
        total = sum(nums)
        # 除首尾外使用Kadane算法找到非环形子数组的最小和，从而计算环形子数组的最大和
        whole1 = total
        curr = float('inf')
        for num in nums[1:n-1]:
            if curr > 0:
                curr = num
            else:
                curr += num
            if (total-curr) > whole1:
                whole1 = total-curr
        
        if total > whole1:
            whole1 = total
        
        # 返回两种情况的最大值
        return whole0 if whole0>whole1 else whole1

Explore

在环形数组中，若选择包含环状连接的子数组，实际上是选择了数组两端的元素同时排除了数组中间某段元素。所以，计算这种情况下的最大子数组和可以转换为求整个数组的总和减去中间某段的最小子数组和。这样，剩余部分即为所求的包含环状连接的最大子数组和。

如果数组全部元素为负数，使用Kadane算法找到的最小子数组和可能等于整个数组的总和。此时从总和中减去这个最小子数组和结果为0。然而，最优解应为单个最小负数值，而非0。因此，在全负数情况下，直接使用Kadane算法找到的非环形最大子数组和（即最大单个元素）为最终结果，无需进行环形考虑。

跳过数组的首尾元素是为了避免整个数组被视为一个非环形的部分，这是因为我们的目的是找出一个真正的中间部分来减去。如果包括首尾元素，则可能出现计算得到的最小子数组和为整个数组的情况，这将违背寻找环形子数组的初衷（至少需要包含数组的一部分环形连接）。

在题解中，通过特意不包括数组的第一个和最后一个元素来找最小子数组和的方式，避免了选取整个数组作为最小子数组的可能。这样确保了所减去的部分不会是整个数组的总和，从而保证了非空的子数组。这是为了正确地计算包含环形连接的子数组的最大和。