Maximum Sum Circular Subarray

January 23, 2024

Problem Statement #

Given a circular integer array nums (the last element is connected to the first element), find the maximum possible sum of a non-empty subarray of nums.

Example:

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

Solution Approach #

The solution involves finding the maximum subarray sum using Kadane’s algorithm. Since the array is circular, the maximum sum may wrap around the end of the array. Therefore, we also find the minimum subarray sum using Kadane’s algorithm and subtract it from the total sum to get the maximum sum that wraps around.

Algorithm Steps #

1. Apply Kadane’s algorithm to find the maximum subarray sum.
2. Apply Kadane’s algorithm to find the minimum subarray sum.
3. Calculate the total sum of the array.
4. The maximum circular subarray sum is the maximum of the maximum subarray sum and total sum - minimum subarray sum.
5. Special case: If all numbers are negative, return the maximum subarray sum.
6. Return the maximum circular subarray sum.

Code (Python) #

def maxSubarraySumCircular(nums):
    def kadane(gen):
        max_sum = cur_sum = next(gen)
        for x in gen:
            cur_sum = x + max(cur_sum, 0)
            max_sum = max(max_sum, cur_sum)
        return max_sum

    total_sum = sum(nums)
    max_sum = kadane(iter(nums))
    min_sum = kadane(-x for x in nums[1:] + nums[:-1])
    
    return max(max_sum, total_sum + min_sum) if max_sum > 0 else max_sum

# Test the function
print(maxSubarraySumCircular([5, -3, 5]))  # Output: 10

Time Complexity #

O(n), where n is the number of elements in nums. The array is processed twice.

Space Complexity #

O(1), as only a constant amount of extra space is used.