What is the best approach for Maximum Sum Circular Subarray?

Use Kadane's algorithm for linear subarrays combined with total minus minimum subarray sums for circular wraparounds, ensuring O(N) time and O(1) space.

How do you handle arrays with all negative numbers?

Return the largest single element found by linear Kadane's algorithm since the circular total-minus-minimum approach would incorrectly yield zero.

Can this solution work in constant space?

Yes, only running sums, maximum, minimum, and total variables are needed, avoiding extra arrays or dynamic programming tables.

Why subtract the minimum subarray from the total array sum?

This computes the maximum sum for wraparound subarrays by excluding the contiguous minimum portion and effectively including the rest of the array.

Is this problem an example of state transition dynamic programming?

Yes, the solution relies on updating running sums (states) and transitioning them optimally to maintain maximum and minimum subarray sums across the array.

#918

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空子数组的最大可能和。环形数组意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % …

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

题目描述

给定一个长度为 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 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴

lightbulb

解题思路

方法一：维护前缀最值

求环形子数组的最大和，可以分为两种情况：

情况一：最大和的子数组不包含环形部分，即为普通的最大子数组和；
情况二：最大和的子数组包含环形部分，我们可以转换为：求数组总和减去最小子数组和。

因此，我们维护以下几个变量：

前缀和最小值 $pmi$ ，初始值为 $0$ ；
前缀和最大值 $pmx$ ，初始值为 $-\infty$ ；
前缀和 $s$ ，初始值为 $0$ ；
最小子数组和 $smi$ ，初始值为 $\infty$ ；
答案 $ans$ ，初始值为 $-\infty$ 。

接下来，我们只需要遍历数组 $nums$ ，对于当前遍历到的元素 $x$ ，我们做以下更新操作：

更新前缀和 $s = s + x$ ；
更新答案 $ans = \max(ans, s - pmi)$ ，即为情况一的答案（前缀和 $s$ 减去最小前缀和 $pmi$ ，可以得到最大子数组和）；
更新 $smi = \min(smi, s - pmx)$ ，即为情况二的最小子数组和；
更新 $pmi = \min(pmi, s)$ ，即为最小前缀和；
更新 $pmx = \max(pmx, s)$ ，即为最大前缀和。

遍历结束，我们取 $ans$ 以及 $s - smi$ 的最大值作为答案返回即可。

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        pmi, pmx = 0, -inf
        ans, s, smi = -inf, 0, inf
        for x in nums:
            s += x
            ans = max(ans, s - pmi)
            smi = min(smi, s - pmx)
            pmi = min(pmi, s)
            pmx = max(pmx, s)
        return max(ans, s - smi)

speed

复杂度分析

指标	值
时间	complexity is O(N) since we traverse the array twice: once for linear max and once for minimum subarray. Space complexity is O(1) as only running totals and max/min values are stored.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Ask for a solution using dynamic programming to show understanding of state transitions in arrays.
question_mark
Expect discussion of both linear and circular subarrays and handling edge cases like all-negative numbers.
question_mark
Look for an O(N) solution that combines Kadane's algorithm with total-minus-minimum logic.

warning

常见陷阱

外企场景

error
Failing to consider circular wraparound cases where the subarray includes the array's start and end.
error
Incorrectly handling arrays where all numbers are negative, which can break the total-minus-minimum approach.
error
Using extra space unnecessarily instead of maintaining constant space with running totals.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimum sum circular subarray instead of the maximum, flipping the linear and total-minus-minimum logic.
arrow_right_alt
Apply the same approach to 2D circular arrays with row-wise and column-wise Kadane adaptations.
arrow_right_alt
Compute maximum sum subarrays with a fixed length window in a circular array, requiring sliding window modifications.

help

常见问题

外企场景

继续练习

#1425 带限制的子序列和 #1687 从仓库到码头运输箱子 #1696 跳跃游戏 VI