0

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.

Improve this question

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Max subarray = 1 -1 1. Min subarray = -1 1 -1. Or either of those with only 1 element for the other one. I didn't get that at first, so putting it here in case someone else doesn't either.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.