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 non-empty 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 non-empty, 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 one-interval subarrays, or two-interval subarrays, depending on how many intervals of the fixed-size 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 one-interval subarrays, so it only remains to consider two-interval subarrays.

Let's say the intervals are . Let's try to compute the i-th candidate: the largest possible sum of a two-interval subarray for a given . Computing the part of the sum is easy. Let's write

and

so that the desired i-th 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 j-th 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 j-th 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 one-interval subarrays, or two-interval subarrays.

Using Kadane's algorithm kadane for finding the maximum sum of non-empty subarrays, the answer for one-interval subarrays is kadane(A).

Now, let . For a two-interval subarray like:

we can write this as

For two-interval subarrays, let be the array with each element multiplied by . Then the answer for two-interval 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 one-interval subarrays (which we can use Kadane's algorithm), or two-interval 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 kadane-min algorithm to minimize the "interior" part of the sum.

Again, because the interior must be non-empty, 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.