Как найти наименьший непрерывный подмассив с максимальной суммой?

Question

Алгоритм Кадане может найти нам максимальную непрерывную сумму подмассива, а также начальный и конечный индексы, но непрерывный подмассив не обязательно всегда наименьший. Например: 10 5 -12 7 -10 20 30 -10 50 60. Совокупная сумма всего массива равна 150. Совокупная сумма последних 5 элементов также равна 150. Как бы вы изменили алгоритм, чтобы найти наименьший подмассив?

Answer 1

Мы можем решить это за O(n) двумя обходами. При первом обходе используйте алгоритм Кадане, чтобы найти максимальную сумму S. Для второго обхода хорошее описание на https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/solution/ состоит в том, чтобы поддерживать двустороннюю очередь индексов для сумм префиксов массива, чтобы иметь возможность хранить индексы в монотонно увеличивающемся списке prefix_left, который мы можем сравнить с prefix_right (текущий индекс), вычтенным из S. Мы ищем самые маленькие r - l такие, что prefixes[l] ≤ prefixes[r] - S. Пока prefixes[l] ≥ prefixes[r], хлопните налево. Затем, в то время как prefixes[l] ≤ prefixes[r] - S обновит решение и выскочит влево (поскольку любой больший индекс r будет генерировать только больший интервал по сравнению с тем же l). Добавьте y в очередь.