Maximum Sum Circular Subarray

Q: What is the time complexity of Maximum Sum Circular Subarray?

O(n). The algorithm iterates through the array once, updating running sums and tracking maximum and minimum subarray sums, resulting in linear time complexity.

Q: What pattern does Maximum Sum Circular Subarray use?

The Pattern: Dynamic Programming (Kadane's Algorithm with Circular Array Adaptation) The Heuristic: When dealing with maximum subarray sums in circular arrays, the problem splits into two cases: the maximum subarray is either fully contained (linear Kadane) or wraps around the ends (total sum minus minimum subarray). Computing both maximum and minimum subarrays in one pass enables an O(n) solution that elegantly handles circularity.

Medium Dynamic Programming

Problem

Given a circular integer array nums, return the maximum possible sum of a non-empty subarray of nums.

1 ≤ nums.length ≤ 3 * 10⁴
−3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴

Example

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

Output: 3

The maximum subarray sum without wrapping is 3 (subarray [3]). The maximum subarray sum with wrapping is 1 + (-2) + (-2) = -3, which is less than 3. Thus, the answer is 3. The algorithm computes the total sum, the maximum subarray sum using Kadane's algorithm, and the minimum subarray sum similarly. Since the array is circular, the maximum sum could be either the maximum subarray sum found directly or the total sum minus the minimum subarray sum (which corresponds to the maximum sum of the wrapped subarray). The critical insight is to consider both cases and choose the maximum.

Approach

Straightforward Solution

A brute-force approach would consider all subarrays including those that wrap around, resulting in O(n^2) or worse time complexity, which is infeasible for large inputs.

Core Observation

The maximum subarray sum in a circular array is either the maximum subarray sum in the linear array or the total sum minus the minimum subarray sum (which corresponds to the maximum sum of the wrapped subarray). This duality arises because wrapping the subarray is equivalent to excluding a minimum subarray in the middle.

Path to Optimal

Preview

The key recognition signals are 'maximum subarray sum' and 'circular array'. These indicate Dynamic Programming because the problem breaks down into finding maximum and minimum subarray sums using Kadane's algorithm…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use Kadane's algorithm to find the maximum subarray sum and minimum subarray sum in one pass while accumulating the total sum. If the maximum subarray sum is negative, it means all numbers are negative, so return the maximum subarray sum directly…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the array once, updating running sums and tracking maximum and minimum subarray sums, resulting in linear time complexity.

Space

O(1)

Only a fixed number of variables are used to track sums and maxima/minima, so the auxiliary space is constant regardless of input size.

Pattern Spotlight

Dynamic Programming (Kadane's Algorithm with Circular Array Adaptation)

When dealing with maximum subarray sums in circular arrays, the problem splits into two cases: the maximum subarray is either fully contained (linear Kadane) or wraps around the ends (total sum minus minimum subarray). Computing both maximum and minimum subarrays in one pass enables an O(n) solution that elegantly handles circularity.

Solution

Python

1class Solution:
2    def maxSubarraySumCircular(self, nums: list[int]) -> int:
3        total = nums[0]
4
5        curr_max = nums[0]
6        best_max = nums[0]
7
8        curr_min = nums[0]
9        best_min = nums[0]
10
11        for i in range(1, len(nums)):
12            num = nums[i]
13            total += num
14
15            curr_max = max(num, curr_max + num)
16            best_max = max(best_max, curr_max)
17
18            curr_min = min(num, curr_min + num)
19            best_min = min(best_min, curr_min)
20
21        if best_max < 0:
22            return best_max
23
24        return max(best_max, total - best_min)

Step-by-Step Solution

Accumulate Total and Track Maximum and Minimum Subarray Sums

3total = nums[0]
5curr_max = nums[0]
6best_max = nums[0]
8curr_min = nums[0]
9best_min = nums[0]
11for i in range(1, len(nums)):
12    num = nums[i]
13    total += num
15    curr_max = max(num, curr_max + num)
16    best_max = max(best_max, curr_max)
18    curr_min = min(num, curr_min + num)
19    best_min = min(best_min, curr_min)

Objective

To compute the total sum of the array while simultaneously finding the maximum and minimum subarray sums using Kadane's algorithm variants.

Key Insight

Kadane's algorithm efficiently finds the maximum subarray sum by tracking the current maximum sum ending at each position. Similarly, tracking the minimum subarray sum allows identifying the subarray that, when excluded, yields the maximum wrapped subarray sum. By combining these computations in a single pass, the algorithm leverages the relationship between total sum, maximum subarray, and minimum subarray to solve the circular problem efficiently.

Interview Quick-Check

Core Logic

Kadane's algorithm is applied twice in one pass: once to find the maximum subarray sum and once to find the minimum subarray sum, while accumulating the total sum.

State & Boundaries

Initialize current and best max/min sums to the first element to handle arrays with all negative numbers correctly.

Common Pitfalls & Bugs

Failing to update total sum or mixing max and min calculations can lead to incorrect results.

Complexity

This single-pass approach ensures O(n) time and O(1) space complexity.

Handle All Negative Numbers and Return Final Maximum Sum

To handle the edge case where all numbers are negative and return the correct maximum subarray sum, otherwise return the maximum between the linear max subarray sum and the wrapped subarray sum.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 15 Critical

curr_max = max(num, curr_max + num)

Update current maximum subarray sum ending at this element.

This line embodies Kadane's algorithm's core logic, deciding whether to start a new subarray at the current element or extend the existing one, which is essential for finding the maximum subarray sum efficiently.

Line 18 Critical

curr_min = min(num, curr_min + num)

Update current minimum subarray sum ending at this element.

This line applies the minimum variant of Kadane's algorithm, deciding whether to start a new minimum subarray or extend the existing one, which is crucial for computing the wrapped subarray sum.

Line 21 Critical

if best_max < 0:

Check if the maximum subarray sum is negative (all elements negative).

This condition identifies the all-negative scenario, ensuring the algorithm returns the correct maximum subarray sum without incorrectly using the wrapped sum formula.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why do we return the maximum between the maximum subarray sum and total sum minus the minimum subarray sum?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Maximum Sum Circular Subarray from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Maximum Sum Circular Subarray drill

or drill a free problem

1	`class Solution:`
2	`def maxSubarraySumCircular(self, nums: list[int]) -> int:`
3	`total = nums[0]`
4
5	`curr_max = nums[0]`
6	`best_max = nums[0]`
7
8	`curr_min = nums[0]`
9	`best_min = nums[0]`
10
11	`for i in range(1, len(nums)):`
12	`num = nums[i]`
13	`total += num`
14
15	`curr_max = max(num, curr_max + num)`
16	`best_max = max(best_max, curr_max)`
17
18	`curr_min = min(num, curr_min + num)`
19	`best_min = min(best_min, curr_min)`
20
21	`if best_max < 0:`
22	`return best_max`
23
24	`return max(best_max, total - best_min)`

3	`total = nums[0]`
5	`curr_max = nums[0]`
6	`best_max = nums[0]`
8	`curr_min = nums[0]`
9	`best_min = nums[0]`
11	`for i in range(1, len(nums)):`
12	`num = nums[i]`
13	`total += num`
15	`curr_max = max(num, curr_max + num)`
16	`best_max = max(best_max, curr_max)`
18	`curr_min = min(num, curr_min + num)`
19	`best_min = min(best_min, curr_min)`