Как я могу найти максимальную сумму подпоследовательности с помощью динамического программирования?

Я перечитываю Руководство по разработке алгоритмов Скиены, чтобы наверстать упущенное из того, что забыл со школы, и меня немного сбивают с толку его описания динамического программирования. Я поискал это в Википедии и на других сайтах, и, хотя все описания имеют смысл, у меня возникают проблемы с выяснением конкретных проблем. В настоящее время я работаю над задачей 3-5 из книги Skiena. (Имея массив из n действительных чисел, найдите максимальную сумму в любом смежном подвекторе входных данных.) У меня есть решение O (n ^ 2), такое, как описано в , этот ответ . Но я застрял на решении O (N) с использованием динамического программирования. Мне не ясно, каким должно быть отношение повторения.

Я вижу, что подпоследовательности образуют набор сумм, например:

S = {a, b, c, d}

a    a+b    a+b+c    a+b+c+d
     b      b+c      b+c+d
            c        c+d
                     d

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

Мне также напоминают таблицы суммированных площадей. Вы можете рассчитать все суммы, используя только кумулятивные суммы: a, a + b, a + b + c, a + b + c + d и т. Д.(Например, если вам нужно b + c, это просто (a + b + c) - (a).) Но не ищите O (N) способа получить это.

Может ли кто-нибудь объяснить мне, что такое решение динамического программирования O (N) для этой конкретной проблемы? Я чувствую, что почти понимаю, но что-то упускаю.