#918

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Sum Circular Subarray

Find the maximum sum of a circular subarray using state transition dynamic programming, optimizing for wraparound cases efficiently.

array divide and conquer dynamic programming queue monotonic queue

Problem Statement

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray. A circular array connects the end to the beginning, so subarrays can wrap around the array's boundary. Each element may appear at most once in the chosen subarray.

Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element is nums[(i - 1 + n) % n]. Identify the subarray that yields the highest sum, considering both standard contiguous ranges and ranges that wrap around the end to the start of the array.

Examples

Example 1

Input: nums = [1,-2,3,-2]

Output: 3

Subarray [3] has maximum sum 3.

Example 2

Input: nums = [5,-3,5]

Output: 10

Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3

Input: nums = [-3,-2,-3]

Output: -2

Subarray [-2] has maximum sum -2.

Constraints

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

Solution Approach

Linear Maximum Subarray via Kadane's Algorithm

Apply standard Kadane's algorithm to find the maximum sum of a non-circular subarray. Track the current running sum and update the maximum found so far. This captures cases where the optimal subarray does not wrap around.

Compute Circular Maximum Using Total Minus Minimum

To account for wraparound subarrays, compute the total sum of the array and find the minimum subarray sum with a reversed Kadane's approach. Subtracting this minimum from the total yields the maximum circular subarray sum that spans the array's boundary.

Combine Results and Handle All-Negative Edge Case

The final maximum is the higher of the linear max sum and circular max sum. If all elements are negative, the minimum subarray equals the total, so directly use the linear max sum. This ensures correctness across negative-dominated inputs.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Maintain Prefix Maximum

The maximum sum of a circular subarray can be divided into two cases:

1

2

3

4

5

6

7

8

9

10

11

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)

Continue Practicing

#1425 constrained subsequence sum #1687 delivering boxes from storage to ports #1696 jump game vi