Intersection of maximum and minimum subarrays

Question

Suppose we have an array of some integers (can be both +ve and -ve).

We find non-empty maximum and minimum subarrays(subarrays have successive elements only) from this.

My claim is that these subarrays either are disjoint(no common element) OR one totally contains the other. There cannot be anything like partial intersection.

Is this claim true? If not can you give a counter-example?

Example case: 13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7

max subarray is from 8th to 11th element having sum 43. min subarray is from 2nd to 7th element having sum -50.

Answer 1

If you consider the following integer array of length 4

1 -1 1 -1

then the max subarray has sum 1, and the min subarray has sum -1. However, both the max and the min occur twice, and with one choice, they do intersect. So as it stands, the claim is false.

However, if you restrict to the shortest subarray, I think the claim is true. Alternatively, if you say that any overlap must have a sum of zero then it's true.

The easiest way to prove is to note that the sum of the overlap must be zero. If the sum of the overlap wasn't zero, then discarding the overlap region from either the max subarray of the min subarray will produce a higher max or a smaller min. That contradicts the assertion that max and min subarrays are what they claim to be, hence the sum of the overlap cannot be non-zero.