Maximum Sum Circular Subarray - Leetcode Solution

The Maximum Sum Circular Subarray problem on LeetCode can be solved using the Kadane's algorithm and a little bit of modification to handle the circular subarray case. The problem statement is as follows:

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

Example:

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

Algorithm:

1. Find the maximum subarray sum using Kadane's algorithm. This will give the maximum sum when there are no circular shifts.

2. Find the minimum subarray sum using the same algorithm but by negating the array elements. This will give us the minimum sum when there are no circular shifts.

3. Compute the total sum of the array.

4. Compute the circular sum by subtracting the minimum sum from the total sum. This will give us the maximum sum when there is one circular shift.

5. Return the maximum of step 1 and step 4.

Pseudo code:

def maxSubarraySumCircular(nums): max_sum = nums[0] min_sum = nums[0] curr_max = nums[0] curr_min = nums[0] total_sum = nums[0] n = len(nums)

# Compute the maximum and minimum subarray sums
for i in range(1, n):
    curr_max = max(curr_max + nums[i], nums[i])
    max_sum = max(max_sum, curr_max)
    
    curr_min = min(curr_min + nums[i], nums[i])
    min_sum = min(min_sum, curr_min)
    
    total_sum += nums[i]

# Compute the circular sum
circular_sum = total_sum - (-min_sum) # Negate min_sum to convert it to max_sum

# Return the maximum of normal and circular subarray sums
return max(max_sum, circular_sum)

Time complexity: O(n)

Space complexity: O(1)

1