Нахождение двух списков фиксированных размеров (K, L), чтобы максимизировать общую сумму среди положительной последовательности

Question

Учитывая список натуральных чисел и два целых числа K и L , мне нужно выбрать два непересекающихся смежных подсписка длины K и L , чтобы максимизировать объединенную сумму двух подсписков.

Например, если список [6,1,4,6,3,2,7,4], K = 3 и L = 2, тогда я хочу получить подсписки [4,6,3] и [7,4], чья суммарная сумма 24 является максимально достижимой.

Список содержит не менее K + L элементов и не более 600 элементов;элементы являются целыми числами в диапазоне [1, 500].

Я не знаю, с чего начать.Я думаю, что решение динамического программирования, но я не очень знаком с ним, поэтому я не уверен, что это путь.

Answer 1

Сканирование массива слева направо, вычисление частичных сумм для непрерывных подмассивов длины K и длины L, начиная с каждого индекса.Это может быть выполнено в O (n).

Записать самые большие суммы до каждого индекса во вспомогательные массивы LeftK, LeftL

Записать самые большие суммы после каждый индекс для вспомогательных массивов RightK, RightL

Теперь для каждого индекса i получите суммы LeftK[i]+RightL[i] и LeftL[i]+RightK[i] и выберите лучшую сумму среди всех записей.