How to Solve Maximum Sum Circular Subarray

This problem requires computing the maximum subarray sum in a circular integer array. The key is combining standard Kadane's algorithm for linear subarrays with a complementary approach for wraparound sums. By tracking both the maximum and minimum subarray sums, you can determine whether the optimal sum spans the array boundary, ensuring O(N) time and constant space complexity.

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

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.

How GhostInterview Helps

• Automatically identifies both linear and circular patterns to compute maximum sums with efficient dynamic programming.
• Highlights failure modes such as all-negative arrays and ensures edge cases are correctly handled.
• Provides step-by-step breakdown connecting Kadane's state transitions to circular subarray logic, reducing trial-and-error coding.

Topic Pages

• Array
• Divide and Conquer
• Dynamic Programming
• Queue
• Monotonic Queue

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.