{x}
blog image

Maximum Sum Circular Subarray

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.

 

Example 1:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

 

Constraints:

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

Solution Explanation for Maximum Sum Circular Subarray

This problem asks to find the maximum sum of a contiguous subarray within a circular array. A circular array means the last element connects to the first, allowing for subarrays that wrap around.

The solution cleverly handles this circularity by considering two cases:

Case 1: Maximum subarray sum without wrap-around. This is a standard maximum subarray sum problem, solvable using Kadane's Algorithm or similar dynamic programming approaches.

Case 2: Maximum subarray sum with wrap-around. This case is where the subarray spans the end and the beginning of the circular array. We can solve this by finding the minimum subarray sum and subtracting it from the total sum of the array. The remaining sum represents the maximum sum of the subarray that wraps around. The intuition is that the minimum subarray sum represents the portion to exclude to maximize the wrap-around sum.

The optimal solution efficiently combines these two cases in a single pass through the array.

Algorithm:

  1. Initialization:

    • pmi: Minimum prefix sum (initialized to 0).
    • pmx: Maximum prefix sum (initialized to negative infinity).
    • ans: Maximum sum found so far (initialized to negative infinity).
    • s: Current prefix sum (initialized to 0).
    • smi: Minimum subarray sum (initialized to positive infinity).

  2. Iteration: Iterate through the nums array:

    • Update the prefix sum: s += x (where x is the current element).
    • Update ans: ans = max(ans, s - pmi). This finds the maximum subarray sum without wrap-around (Case 1).
    • Update smi: smi = min(smi, s - pmx). This tracks the minimum subarray sum for Case 2.
    • Update pmi: pmi = min(pmi, s).
    • Update pmx: pmx = max(pmx, s).

  3. Result: Return the maximum of ans (Case 1) and s - smi (Case 2). s - smi represents the maximum sum with wrap-around.

Time and Space Complexity:

  • Time Complexity: O(n), as we iterate through the array once.
  • Space Complexity: O(1), as we use only a constant number of variables.

Code Implementation (Python):

def maxSubarraySumCircular(nums):
    pmi, pmx = 0, float('-inf')  # Initialize minimum and maximum prefix sums
    ans, s, smi = float('-inf'), 0, float('inf')  # Initialize answer, current sum, and minimum subarray sum
 
    for x in nums:
        s += x
        ans = max(ans, s - pmi)  # Update max sum (no wrap-around)
        smi = min(smi, s - pmx)  # Update min subarray sum (for wrap-around)
        pmi = min(pmi, s)  # Update min prefix sum
        pmx = max(pmx, s)  # Update max prefix sum
 
    return max(ans, s - smi)  # Return max of both cases

The implementations in other languages (Java, C++, Go, TypeScript) follow the same logic, with only syntax differences. The core algorithm remains the same for optimal efficiency.