Max continuous subarray sum + minimum continuous subarray sum = total sum in a circular array I have an array $A$. This array is circular. By this, I mean you can arrange the array in a circle such that the end of the array is connected to the beginning of the array.
I want to prove that $T$, the total sum of the array, is equal to the minimum continuous subarray sum plus the maximum continuous subarray sum.
For example, consider $A = [5, -1, 5]$. $T = 9$. The minimum continuous subarray sum here is the single element -1. The maximum continuous subarray sum here is the 5 at the end of $A$ and the 5 at the beginning of $A$ (recall $A$ is circular), totaling 10.
So $T = 9 = -1 + 10 = 9$.
How can I prove this formally? It makes sense in my head that the statement is true, but I can't quite justify it.
 A: Since your array is circular, it's best to consider indices $\mod n$, where $n$ is the length of your array. So normally you would name the elements $A_0, A_1, A_2, \ldots, A_{n-1}$, but we can also talk about $A_n$ (which is identical to $A_0$), a.s.o.
A continuous subarray now is something like $A_k,A_{k+1},\ldots, A_{k+r-1}$ with $r\in \{0,\ldots, n\}$, with $r$ the length of that subarray. Note that $r=0$ corresponds to the empty subarray, $r=n$ is the complete array.
Note that each continuous subarray A has a complement $c(A)$, containing the other elements of $A$: $c(A)=A_{k+r},A_{k+r+1},\ldots,A_{k+n-1}$, which is also a continuous sbuarray. Also note that the complement of the complement is again the original subarray.
It's obvious that the sum of elements of a continuous subarray (let's call it $s(A)$ for a subset $A$) and it's complement is $T$, because it's just all the elements of A added together.
So if you have a minimum continuous subarray $X$, I claim that it's complement $c(X)$ is a maximum continuous subarray. Why is that?
We have $s(X)+s(c(X))=T$ as noted above. If there was a continuous subarray $Y$ with $s(Y) > s(c(X))$, then we can look at the complement of $Y$! We have again $s(Y)+s(c(Y))=T$, so we get
$$ s(c(Y)) = T - s(Y) < T - s(c(X)) = s(X),$$
which means $c(Y)$ has a smaller sum of elements than $X$, which is a contradiction to the choice of $X$. So there can't be such a $Y$, so we proved that $c(X)$ is a maximum continuous subarray, which proves the result you want:
$$s(X)+s(c(X))=T$$
So your intuition is right, and this proof shows why: minimum and maximum continuous subarrays (there can be more than one) can be paired as complements of each other.
A: First I will rephrase the problem as the numbers are written on a circle.(Since it seems to me easier to visualize).
Now,Say the minimum continuous subarray is A,and the maximum continuous subarray is B.
$\textbf{Case 1:A and B are disjoint}$
Then,there are two sides between $A$ and $B$.Say,left and right.But both the sides should individually sum up to $0$.Otherwise we could extend either A or B.So,the claim follows.
$\textbf{Case 2:They are not disjoint}$
Let $C=A \cap B$. Then,sum of the elements in C must not be negative.Otherwise $A/C$ would have a larger sum than $A$.With similar argument we can say $C$ is not positive.
Hence,the sum of the elements in $C$ is $0$.So,we can instead consider $A/C$ and $B/C$ (since they are also the maximum continuous subarray and minimum one respectively),which reduces the problem to Case 1.
