Is the complement of a Max Prefix Sum a Min Suffix Sum?

Question

Given an array A of n real numbers, are the maximum prefix sum and minimum suffix sum (and vice-versa) of A complements?

I.e. Given A[1..n] and its maximum prefix subarray P[1..i], is its minimum suffix subarray S[j..n] where i+1 = j?

Or stated another way, is sum(A) = maxPrefixSum(A) + minSuffixSum(A) true?

For an array of only negative numbers, let's assume that P is empty and maxPrefixSum(A) = 0. Similar logic applies in the opposite case.

• D.W.: What have you tried? Have you tried working through some examples? Have you tried constructing a proof or counterexample? Have you written a program to try a million random arrays and see if your conjecture holds for all of them?
• Travis: @D.W. I have a conjecture. I was just trying to see if someone else could more easily support it, as I am unsure of the proof. Hence, why I asked the question in the more general sense rather than "review my proof."

Answer 1

It depends on whether the maximum prefix and minimum suffix are unique. Consider for example the array 0ドル$ — you can easily find a counterexample to your claim. Suppose therefore that $\sum_{i \leq j \leq k} A[j] \neq 0$ for all $i \leq k$. Let now $j$ maximize $\sum_{i=1}^j A[i],ドル and let $k$ minimize $\sum_{i=k+1}^n A[i]$. We want to show that $j=k$. Otherwise, there are two cases:

1. If $j < k,ドル let $S = \sum_{i=j}^{k-1} A[i]$. By assumption $S \neq 0$. If $S > 0$ then $\sum_{i=1}^{k-1} A[i] > \sum_{i=1}^j A[i],ドル and otherwise $\sum_{i=j+1}^n A[i] < \sum_{i=k+1}^n A[i]$.

2. If $j > k,ドル let $S = \sum_{i=k}^{j-1} A[i]$. By assumption $S \neq 0$. If $S < 0$ then $\sum_{i=1}^{k-1} A[i] > \sum_{i=1}^j A[i],ドル and otherwise $\sum_{i=j+1}^n A[i] < \sum_{i=k+1}^n A[i]$.