Max Circular Subarray
December 10, 2023
Problem #
Given a circular array, compute its maximum subarray sum in O(n) time. A subarray can be empty, and in this case the sum is 0.
For example, given [8, 1, 3, 4], return 15 as we choose the numbers 3, 4, and 8 where the 8 is obtained from wrapping around.
Given [4, 5, 1, 0], return 6 as we choose the numbers 5 and 1.
Solution #
To solve this problem, we can use Kadane’s algorithm to find the maximum subarray sum for a linear array. However, since the array is circular, we need to consider two cases:
 The maximum sum subarray does not wrap around the end of the array. This can be found using the standard Kadane’s algorithm.
 The maximum sum subarray wraps around the end of the array. To find this, we invert the sign of each element in the array and apply Kadane’s algorithm to find the minimum subarray sum. The maximum sum in this case is the total sum of the array minus this minimum subarray sum.
We then return the maximum of these two sums. However, there’s an edge case: if all numbers in the array are negative, the maximum sum is 0, as an empty subarray is allowed.
Let’s write the Python function to implement this logic:
The Python function correctly solves the problem for the given examples:

For the array
[8, 1, 3, 4]
, the maximum subarray sum is15
, achieved by choosing the numbers3
,4
, and8
(where8
is obtained from wrapping around). 
For the array
[4, 5, 1, 0]
, the maximum subarray sum is6
, achieved by choosing the numbers5
and1
.
This solution runs in ( O(n) ) time, as required.
def maxSubarraySumCircular(arr):
def kadane(arr):
max_ending_here = max_so_far = arr[0]
for x in arr[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
# Case 1: get the maximum sum using standard kadane's algorithm
max_kadane = kadane(arr)
# Case 2: Now find the maximum sum that includes corner elements.
max_wrap = 0
for i in range(len(arr)):
max_wrap += arr[i] # Calculate arraysum
arr[i] = arr[i] # invert the array (change sign)
# Max sum with corner elements will be:
# arraysum  (max subarray sum of inverted array)
max_wrap = max_wrap + kadane(arr)
# The maximum circular sum will be maximum of two sums
if max_wrap > max_kadane and max_wrap != 0:
return max_wrap
else:
return max_kadane
# Example usage:
example1 = [8, 1, 3, 4]
example2 = [4, 5, 1, 0]
print(maxSubarraySumCircular(example1)) # Output: 15
print(maxSubarraySumCircular(example2)) # Output: 6
This code implements Kadane’s algorithm for both the standard max subarray sum and the modified version for circular arrays. It handles the case where the maximum sum subarray either does not wrap around the array or does wrap around.