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

Question

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

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

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

Действительно ли это утверждение? Если вы не можете дать встречный пример?

Пример случай: -3 -25 13 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7

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

Answer 1

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

1 -1 1 -1 

то максимальная подмассив имеет сумму 1, и имеет минимальное подмассив сумму -1. Однако как max, так и min происходят дважды, и с одним выбором они пересекаются. Таким образом, это утверждение неверно.

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

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