1

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.

2 Answers2

1

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.

Ingix
  • 14,494
0

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.

Yes it's me
  • 1,854
  • 6
  • 15