Maximum Sum Circular Subarray

Problem Description

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

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i+1], ..., nums[j], there does not exist i ≤ k1, k2 ≤ j with k1 % n == k2 % n.

Examples

Constraints

• n == nums.length
• 1 ≤ n ≤ 3 * 10⁴
• -3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴

Two Cases: Normal Kadane or Wrapped

The maximum subarray can fall into one of two configurations:

1. Case A (Normal): the subarray does not wrap around. We find it using standard Kadane’s algorithm.
2. Case B (Circular): the subarray wraps around the boundary (includes a suffix and a prefix).
   • If the subarray wraps, the unselected elements in the middle must form a contiguous subarray with the minimum possible sum.
   • Thus, the maximum circular sum equals total_sum - min_subarray_sum.

The final answer is max(max_subarray_sum, total_sum - min_subarray_sum).

Edge Case: if all numbers in the array are negative, total_sum == min_subarray_sum. The circular formula would yield 0 (an empty subarray, which is forbidden). If max_subarray_sum < 0, we must return max_subarray_sum directly.

Solution: Double Kadane

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int totalSum = 0;
        int currMax = 0, maxSum = nums[0];
        int currMin = 0, minSum = nums[0];

        for (int num : nums) {
            totalSum += num;

            currMax = Math.max(num, currMax + num);
            maxSum = Math.max(maxSum, currMax);

            currMin = Math.min(num, currMin + num);
            minSum = Math.min(minSum, currMin);
        }

        // if all elements are negative, return the normal Kadane max
        if (maxSum < 0) return maxSum;

        return Math.max(maxSum, totalSum - minSum);
    }
}

class Solution:
    def maxSubarraySumCircular(self, nums: list[int]) -> int:
        total_sum = 0
        curr_max = 0
        max_sum = nums[0]
        curr_min = 0
        min_sum = nums[0]

        for num in nums:
            total_sum += num
            
            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)

        # if all elements are negative, return the normal Kadane max
        if max_sum < 0:
            return max_sum

        return max(max_sum, total_sum - min_sum)

#include <vector>
#include <algorithm>
#include <numeric>

class Solution {
public:
    int maxSubarraySumCircular(std::vector<int>& nums) {
        int totalSum = 0;
        int currMax = 0, maxSum = nums[0];
        int currMin = 0, minSum = nums[0];

        for (int num : nums) {
            totalSum += num;

            currMax = std::max(num, currMax + num);
            maxSum = std::max(maxSum, currMax);

            currMin = std::min(num, currMin + num);
            minSum = std::min(minSum, currMin);
        }

        if (maxSum < 0) return maxSum;

        return std::max(maxSum, totalSum - minSum);
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of nums. We perform one pass over the array.
• Space Complexity: O(1).

← All Problems