Maximum Circular Subarray sum

Question

This is a question from the book Algorithms by Jeff Erickson.

Suppose A is a circular array. In this setting, a "contiguous subarray" can be either an interval A[i .. j] or a suffix followed by a prefix A[i .. n] · A[1 .. j]. Describe and analyze an algorithm that finds a contiguous subarray of A with the largest sum. The input array consists of real numbers.

My approach:

There are two possibilities

1.) No Wrapping around (We can use Kadane's Algorithm)

2.) Wrapping around(ie; Starting index of the subarray is greater than the ending index) (I have doubt in this case)

Now return the maximum of two cases as result.

For the second case, searching on the internet provided an approach without proof.

The approach is to find the subarray with minimum sum and subtract it from the sum of the entire array (ie; sum(A) - min_subarray_sum(A)). How is this solution correct?

Link for the method used in the second case: https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 1

Let $A$ be your array, let $B$ a circular subarray of $A$ that maximizes $\sum_{b \in B} b$, and let $C$ be the subarray that contains all elements of $A$ that are not in $B$. Notice that $C$ is also a circular subarray.

You have $\sum_{a \in A} a = \sum_{b \in B} b + \sum_{c\in C} c$, which implies that $\sum_{c \in C} c = \sum_{a \in A} a - \sum_{b \in B} b $. Since $\sum_{a \in A} a $ is a constant (w.r.t. $B$) and $B$ maximizes $\sum_{b \in B} b$, $C$ minimizes $\sum_{c \in C} c$.

Moreover, at least one of $B$ and $C$ is not only circular but also contiguous and can therefore be found in $O(n)$ time.

• Abishek0398: Thanks a lot!!!