Solution
Notes and A Primer on Kadane's Algorithm
About the Approaches
In both Approach 1 and Approach 2, "grindy" solutions are presented that require less insight, but may be more intuitive to those with a solid grasp of the techniques in those approaches. Without prior experience, these approaches would be very challenging to emulate.
Approaches 3 and 4 are much easier to implement, but require some insight.
Explanation of Kadane's Algorithm
To understand the solutions in this article, we need some familiarity with Kadane's algorithm. In this section, we will explain the core idea behind it.
For a given array A
, Kadane's algorithm can be used to find the maximum sum of the subarrays of A
. Here, we only consider nonempty subarrays.
Kadane's algorithm is based on dynamic programming. Let dp[j]
be the maximum sum of a subarray that ends in A[j]
. That is,
Then, a subarray ending in j+1
(such as A[i], A[i+1] + ... + A[j+1]
) maximizes the A[i] + ... + A[j]
part of the sum by being equal to dp[j]
if it is nonempty, and 0
if it is. Thus, we have the recurrence:
Since a subarray must end somewhere, must be the desired answer.
To compute dp
efficiently, Kadane's algorithm is usually written in the form that reduces space complexity. We maintain two variables: ans
as , and cur
as ; and update them as iterates from to .
Then, Kadane's algorithm is given by the following psuedocode:
#Kadane's algorithm ans = cur = None for x in A: cur = x + max(cur, 0) ans = max(ans, cur) return ans
Approach 1: Next Array
Intuition and Algorithm
Subarrays of circular arrays can be classified as either as oneinterval subarrays, or twointerval subarrays, depending on how many intervals of the fixedsize buffer A
are required to represent them.
For example, if A = [0, 1, 2, 3, 4, 5, 6]
is the underlying buffer of our circular array, we could represent the subarray [2, 3, 4]
as one interval , but we would represent the subarray [5, 6, 0, 1]
as two intervals .
Using Kadane's algorithm, we know how to get the maximum of oneinterval subarrays, so it only remains to consider twointerval subarrays.
Let's say the intervals are . Let's try to compute the ith candidate: the largest possible sum of a twointerval subarray for a given . Computing the part of the sum is easy. Let's write
and
so that the desired ith candidate is:
Since we can compute and in linear time, the answer is straightforward after this setup.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Approach 2: Prefix Sums + Monoqueue
Intuition
First, we can frame the problem as a problem on a fixed array.
We can consider any subarray of the circular array with buffer A
, to be a subarray of the fixed array A+A
.
For example, if A = [0,1,2,3,4,5]
represents a circular array, then the subarray [4,5,0,1]
is also a subarray of fixed array [0,1,2,3,4,5,0,1,2,3,4,5]
. Let B = A+A
be this fixed array.
Now say , and consider the prefix sums
Then, we want the largest where .
Now, consider the jth candidate answer: the best possible for a fixed . We want the so that is smallest, with . Let's call this the optimal i for the jth candidate answer. We can use a monoqueue to manage this.
Algorithm
Iterate forwards through , computing the th candidate answer at each step. We'll maintain a queue
of potentially optimal 's.
The main idea is that if and , then we don't need to remember anymore.
Please see the inline comments for more algorithmic details about managing the queue.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Approach 3: Kadane's (Sign Variant)
Intuition and Algorithm
As in Approach 1, subarrays of circular arrays can be classified as either as oneinterval subarrays, or twointerval subarrays.
Using Kadane's algorithm kadane
for finding the maximum sum of nonempty subarrays, the answer for oneinterval subarrays is kadane(A)
.
Now, let . For a twointerval subarray like:
we can write this as
For twointerval subarrays, let be the array with each element multiplied by . Then the answer for twointerval subarrays is .
Except, this isn't quite true, as if the subarray of we choose is the entire array, the resulting two interval subarray would be empty.
We can remedy this problem by doing Kadane twice: once on with the first element removed, and once on with the last element removed.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: in additional space complexity.
Approach 4: Kadane's (Min Variant)
Intuition and Algorithm
As in Approach 3, subarrays of circular arrays can be classified as either as oneinterval subarrays (which we can use Kadane's algorithm), or twointerval subarrays.
We can modify Kadane's algorithm to use min
instead of max
. All the math in our explanation of Kadane's algorithm remains the same, but the algorithm lets us find the minimum sum of a subarray instead.
For a two interval subarray written as , we can use our kadanemin
algorithm to minimize the "interior" part of the sum.
Again, because the interior must be nonempty, we can break up our search into a search on A[1:]
and on A[:1]
.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: in additional space complexity.
Analysis written by: @awice.