최대 및 최소 부분 배열의 교차점

Question

일부 정수 배열이 있다고 가정합니다 (+ ve와 -ve 둘 다 가능).

비어 있지 않음 최대 및 최소 부분 배열 (하위 배열에는 연속 요소 만 있음)이 있습니다.

나의 주장은이 하위 배열들이 서로 겹치지 않고 (공통 요소가 없음) 또는 완전히 다른 배열을 포함하고 있다는 것입니다. 부분 교차와 같은 것은있을 수 없습니다.

이 소유권 주장이 사실입니까? 그렇지 않다면 반대 사례를 줄 수 있습니까?

예 케이스 13 -3 20 -25 -3 -16 -23 18 일 20 -8 12 -22 15 -4 -5 7

최대 서브 어레이는 11 엘리먼트 갖는 합계 43 분으로 8 내지 부분 배열은 합계가 -50 인 2 ~ 7 번째 요소입니다. 만약

1 -1 1 -1 

길이 4의 다음 정수 배열을 고려하면

Answer 1

는 최대 서브 어레이는 합계 1을 가지며, 최소 서브 어레이는 합을 갖는다 -1. 그러나 최대 값과 최소값은 두 번 발생하며 하나의 선택으로 교차합니다. 따라서 그 주장은 거짓입니다.

그러나 가장 짧은 부분 배열로 제한하면 그 주장은 사실이라고 생각합니다. 양자 택일로, 어떤 겹치기라도 0의 합계가 있어야한다고 말하면 그것은 사실입니다.

가장 쉬운 방법은 오버랩의 합이 0이어야한다는 것입니다. 오버랩의 합이 제로가 아닌 경우, 오버랩 영역을 최소 서브 어레이의 최대 서브 어레이로부터 버리면, 최대 또는 최소값이 더 높아진다. 이것은 최대 및 최소 서브 어레이가 주장하는 것임을 주장하는 모순과 모순됩니다. 따라서 오버랩의 합이 0이 될 수 없습니다.