LeetCode 918 - Maximum Sum Circular Subarray

LeetCode Problem 918

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue

Solution

Problem Understanding

The problem asks for the maximum sum of a subarray in a circular array. In simpler terms, we are given a list of integers nums where the end of the list wraps around to the start. We need to find a contiguous section of this list that has the highest sum, keeping in mind that subarrays can "wrap around" from the end to the beginning. The input is an array of integers, which can be both positive and negative, and we must always return a sum from a non-empty subarray.

The constraints tell us that nums can be as long as 30,000 elements, and each element can range from -30,000 to 30,000. This rules out naive solutions that check all possible subarrays, because the number of subarrays grows quadratically with the array length. Important edge cases include arrays where all numbers are negative, arrays with only one element, and arrays where the maximum subarray spans the circular boundary.

In summary, the task is to handle both standard subarray sums and the special case where the subarray wraps around the array, efficiently.

Approaches

A brute-force approach would consider every possible subarray, calculate its sum, and track the maximum. For a circular array, this requires considering subarrays that may start near the end and wrap around to the beginning. While this guarantees correctness, its time complexity is O(n²), which is far too slow for n up to 30,000.

The key insight for an optimal solution is that the maximum subarray sum for a circular array can either be a normal subarray (not wrapping) or a wraparound subarray. For the normal subarray, we can use Kadane's algorithm, which finds the maximum contiguous sum in O(n) time. For the wraparound case, the maximum sum can be derived from the total array sum minus the minimum subarray sum. Subtracting the minimum subarray sum effectively leaves the largest sum that wraps around the ends. This approach leverages Kadane's algorithm twice: once for the maximum sum and once for the minimum sum.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Enumerates all possible subarrays, including wraparound cases
Optimal	O(n)	O(1)	Uses Kadane’s algorithm for both max and min subarrays and total sum subtraction for circular case

Algorithm Walkthrough

1. Calculate the maximum subarray sum using standard Kadane’s algorithm. Iterate through the array while maintaining a running sum. If the running sum becomes negative, reset it to zero. Track the maximum sum encountered.
2. Calculate the minimum subarray sum using a similar Kadane-like approach, but tracking the smallest sum instead. This allows us to compute the circular maximum as the total sum minus this minimum sum.
3. Compute the total sum of the array. This is needed to handle the wraparound scenario.
4. Determine the maximum circular subarray sum. Subtract the minimum subarray sum from the total sum to get the sum of the wraparound subarray.
5. Edge case check: If all numbers are negative, the wraparound computation will incorrectly give zero (total sum minus minimum subarray sum equals zero). In this case, return the maximum element found using the normal Kadane’s algorithm.
6. Return the maximum of the non-wrapping and wrapping sums. This ensures we consider both cases and select the correct maximum.

Why it works: The algorithm works because any subarray in a circular array either wraps around or it doesn’t. Standard Kadane handles the non-wrapping case, while subtracting the minimum subarray sum from the total sum effectively finds the maximum sum of a subarray that wraps around. The edge case ensures correctness when all numbers are negative.

Python Solution

from typing import List

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

        total = 0
        max_sum = float('-inf')
        min_sum = float('inf')
        curr_max = 0
        curr_min = 0

        for num in nums:
            curr_max = max(num, curr_max + num)
            max_sum = max(max_sum, curr_max)

            curr_min = min(num, curr_min + num)
            min_sum = min(min_sum, curr_min)

            total += num

        if max_sum < 0:
            return max_sum

        return max(max_sum, total - min_sum)

This implementation first initializes running variables for total, current maximum, current minimum, and the respective overall max/min sums. It iterates through the array once, updating the running sums and tracking the overall maxima and minima. Finally, it checks for the all-negative edge case and returns the appropriate maximum sum, either non-circular or circular.

Go Solution

func maxSubarraySumCircular(nums []int) int {
    total, maxSum, minSum := 0, nums[0], nums[0]
    currMax, currMin := 0, 0

    for _, num := range nums {
        currMax = max(num, currMax+num)
        maxSum = max(maxSum, currMax)

        currMin = min(num, currMin+num)
        minSum = min(minSum, currMin)

        total += num
    }

    if maxSum < 0 {
        return maxSum
    }

    return max(maxSum, total-minSum)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

In Go, the main difference is explicit handling of max and min through helper functions, and initializing maxSum and minSum with the first element of the array to avoid zero-based edge issues.

Worked Examples

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

Step	curr_max	max_sum	curr_min	min_sum	total
1	1	1	1	1	1
2	-1	1	-2	-2	-1
3	3	3	1	-2	2
4	1	3	-2	-2	0

Wraparound = 0 - (-2) = 2, so max(3, 2) = 3

Example 2: nums = [5, -3, 5]

Step	curr_max	max_sum	curr_min	min_sum	total
1	5	5	5	5	5
2	2	5	-3	-3	2
3	7	7	2	-3	7

Wraparound = 7 - (-3) = 10, max(7,10) = 10

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

Step	curr_max	max_sum	curr_min	min_sum	total
1	-3	-3	-3	-3	-3
2	-2	-2	-2	-3	-5
3	-3	-2	-3	-3	-8

Wraparound = -8 - (-3) = -5, max(-2, -5) = -2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array for both max and min subarrays and total sum computation
Space	O(1)	Only a constant number of variables are used for running totals and maxima/minima

The reasoning is that each element is visited exactly once, and we store only a few integers regardless of array size.

Test Cases

# provided examples
assert Solution().maxSubarraySumCircular([1,-2,3,-2]) == 3  # normal max subarray
assert Solution().maxSubarraySumCircular([5,-3,5]) == 10    # wraparound max subarray
assert Solution().maxSubarraySumCircular([-3,-2,-3]) == -2  # all negative

# boundary and edge cases
assert Solution().maxSubarraySumCircular([1]) == 1          # single element
assert Solution().maxSubarraySumCircular([-1]) == -1        # single negative element
assert Solution().maxSubarraySumCircular([0,0,0]) == 0      # all zeros
assert Solution().maxSubarraySumCircular([3,-1,2,-1]) == 4  # wraparound case
assert Solution().maxSubarraySumCircular