918. 环形子数组的最大和

Difficulty
Medium
Tags
动态规划
单调队列
URL
https://leetcode.cn/problems/maximum-sum-circular-subarray/
Star
给定一个长度为 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​​​​​​​

动态规划

思路
是
🖥️
53. 最大子序和 的进阶版
本题还涉及到了边界，因此分为两种情况
  1. 不包括边界的，按照
    🖥️
    53. 最大子序和     来写
  1. 包括边界的，求最小子数组和，然后sum(nums)-最小子数组和即为答案。
最后范围两种情况的最大值。
notion imagenotion image
题解
class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        dp = [[0]*2 for _ in nums]
        for i in range(0, len(dp)):
            dp[i][0] = -float("inf")
            dp[i][1] = float("inf")
        dp[0][0] = nums[0]
        dp[0][1] = nums[0]
        max_val, min_val = nums[0], nums[0]
        for i in range(1, len(nums)):
            dp[i][0] = max(dp[i-1][0] + nums[i], nums[i])
            dp[i][1] = min(dp[i-1][1] + nums[i], nums[i])
            max_val = max(max_val, dp[i][0])
            min_val = min(min_val, dp[i][1])

        bian_jie = sum(nums)-min_val
        bian_jie = bian_jie if bian_jie != 0 else max(nums)
        zhong_jian = max_val
        
        return max(zhong_jian, bian_jie)

单调队列

思路
参考
💷
862. 和至少为 K 的最短子数组 ，本题要求 和最大的子数组的和。
因此一样的思路：如果当前的前缀和值小于队列尾部的，说明队列尾部的没用了，直接弹出去。
需要注意的是，本题是循环数组，所以长度不能超过len(nums)。
题解
class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        prefix = [0 for _ in range(2 * len(nums) + 1)]
        for i in range(1, len(prefix)):
            prefix[i] = prefix[i-1] + nums[(i-1)%len(nums)]

 
        res = nums[0]
        queue = deque()
        for i in range(0, len(prefix)):
            while queue and i - queue[0] > len(nums):
                queue.popleft()

            if queue:
                res = max(res, prefix[i] - prefix[queue[0]])

            while queue and prefix[i] <= prefix[queue[-1]]:
                queue.pop()
            
            queue.append(i)

        return res