Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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]$.
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]$.
