LeetCode Solutions Blog

Maximum Sum Circular Subarray

Number: 954

Difficulty: Medium

Paid? No

Problem Description

Given a circular integer array nums, return the maximum possible sum of a non-empty subarray. A circular array means that the end of the array connects to the beginning. The subarray can only include each element at most once.

Key Insights

Use Kadane's algorithm to find the maximum sum of a contiguous non-circular subarray.
Apply a modified Kadane's algorithm to find the minimum subarray sum.
The maximum circular subarray sum can be computed as (total sum of array - minimum subarray sum).
Handle the edge case where all numbers are negative by returning the non-circular maximum.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves two passes over the array. In the first pass, we apply Kadane’s algorithm to find the maximum subarray sum. In the second pass, we compute the minimum subarray sum using a similar approach. The maximum circular subarray sum is then the maximum of the non-circular (standard) maximum or (total sum - minimum subarray sum). However, if all numbers are negative, the non-circular maximum is returned to avoid an incorrect result caused by subtracting the minimum subarray sum.

Code Solutions

# Python solution

def maxSubarraySumCircular(nums):
    # Initialize variables for Kadane's algorithm for maximum subarray sum
    max_current = max_global = nums[0]
    # Initialize variables for finding the minimum subarray sum
    min_current = min_global = nums[0]
    # Calculate total sum starting with the first element
    total_sum = nums[0]
    
    # Iterate over the array from the second element
    for num in nums[1:]:
        total_sum += num  # Update total sum
        
        # Update maximum subarray sum ending at current position
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
        
        # Update minimum subarray sum ending at current position
        min_current = min(num, min_current + num)
        min_global = min(min_global, min_current)
    
    # If all numbers are negative, max_global is the maximum
    if max_global < 0:
        return max_global
    else:
        # Otherwise, the answer is the maximum of non-circular and circular case
        return max(max_global, total_sum - min_global)

# Example usage:
print(maxSubarraySumCircular([1, -2, 3, -2]))