Пересечение максимального и минимального подмассивов

Предположим, у нас есть массив некоторых целых чисел (может быть как +ve, так и -ve).

Отсюда мы находим непустые максимальный и минимальный подмассивы (подмассивы имеют только последовательные элементы).

Я утверждаю, что эти подмассивы либо не пересекаются (нет общего элемента), либо один полностью содержит другой. Не может быть ничего похожего на частичное пересечение.

Верно ли это утверждение? Если нет, можете привести контрпример?

Пример: 13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7

максимальный подмассив состоит из элементов с 8-го по 11-й, имеющих сумму 43. минимальный подмассив состоит из элементов со 2-го по 7-й, имеющих сумму -50.


arrays array-algorithms sub-array
person Swapniel    schedule 08.06.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Если вы рассмотрите следующий целочисленный массив длины 4

1 -1 1 -1

тогда максимальный подмассив имеет сумму 1, а минимальный подмассив имеет сумму -1. Однако и max, и min встречаются дважды, и при одном выборе они пересекаются. Итак, в нынешнем виде утверждение ложно.

Однако, если вы ограничитесь кратчайшим подмассивом, я думаю, что утверждение верно. В качестве альтернативы, если вы говорите, что сумма любого перекрытия должна быть равна нулю, тогда это правда.

Самый простой способ доказать — заметить, что сумма перекрытий должна быть равна нулю. Если сумма перекрытий не равна нулю, то отбрасывание области перекрытия либо из подмассива max, либо из подмассива min приведет к большему максимуму или меньшему минимуму. Это противоречит утверждению о том, что подмассивы max и min являются тем, за что себя выдают, следовательно, сумма перекрытий не может быть отличной от нуля.

person Stochastically    schedule 08.06.2013
comment
Максимальный подмассив = 1 -1 1. Минимальный подмассив = -1 1 -1. Или любой из тех, у кого только 1 элемент для другого. Сначала я этого не понял, поэтому поместил сюда, если кто-то тоже не понял. - person Bernhard Barker; 09.06.2013