1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Jan 29 '17 at 0:59
  • $\begingroup$ @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." $\endgroup$ – Travis Jan 29 '17 at 6:40
1
$\begingroup$

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]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.