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

Question

Я перечитываю Руководство по разработке алгоритмов Скиены, чтобы узнать некоторые вещи, которые я забыл со школьной скамьи, и я немного сбит с толку его описаниями динамического программирования.Я посмотрел его в Википедии и на других сайтах, и хотя все описания имеют смысл, у меня возникают проблемы с определением конкретных проблем.В настоящее время я работаю над проблемой 3-5 из книги Скиены.(Учитывая массив из 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) динамического программирования для этой конкретной проблемы?Я чувствую, что почти понял, но что-то упускаю.

Answer 1

Вы должны взглянуть на этот pdf вернуться в школу в http://castle.eiu.edu вот оно:

Объяснение следующего псевдокода также находится в pdf.

Answer 2

Существует решение, например, сначала отсортировать массив в некоторую вспомогательную память, затем применить метод Longest Common Sub-Sequence к исходному массиву и отсортированному массиву с суммой (не длиной) общей подпоследовательности в 2 массива как запись в таблицу (Memoization). Это также может решить проблему

Общее время работы O (nlogn) + O (n ^ 2) => O (n ^ 2) Пробел есть O (n) + O (n ^ 2) => O (n ^ 2)

Это не очень хорошее решение, когда память входит в изображение. Это просто, чтобы дать представление о том, как проблемы могут быть сведены друг к другу.

Answer 3

Мое понимание DP - это "составление таблицы".Фактически, первоначальное значение «программирование» в DP - это просто создание таблиц.

Ключ в том, чтобы выяснить что поместить в таблицу , или современные термины: какое состояние отслеживатьили каков ключ / значение вершины в DAG (игнорируйте эти термины, если они кажутся вам странными).

Как насчет выбора dp[i] таблицы, являющейся самой большой суммой, заканчивающейся индексом i измассив, например, массив [5, 15, -30, 10]

Вторым важным ключом является «оптимальная подструктура», то есть «предположить», что dp[i-1] уже хранит наибольшую сумму дляподпоследовательности, оканчивающиеся на индекс i-1 , поэтому единственный шаг на i состоит в том, чтобы решить, следует ли включать a[i] в подпоследовательность или нет

dp[i] = max(dp[i-1], dp[i-1] + a[i])

Первый термин в max - «не включать [i]», второй термин - «включать [i]».Обратите внимание, если мы не включим a[i], самая большая сумма до сих пор остается dp[i-1], которая получается из аргумента «оптимальной подструктуры».

Таким образом, вся программа выглядит так (в Python):

a = [5,15,-30,10]

dp = [0]*len(a)
dp[0] = max(0,a[0]) # include a[0] or not

for i in range(1,len(a)):
    dp[i] = max(dp[i-1], dp[i-1]+a[i]) # for sub-sequence, choose to add or not     


 print(dp, max(dp)) 

Результат: наибольшая сумма подпоследовательности должна быть самым большим элементом в таблице dp, после i перебирать массив a.Но внимательно посмотрите на dp, он содержит всю информацию.

Поскольку он только один раз проходит через элементы в массиве a, это алгоритм O (n).

Эта проблема кажется глупой, поскольку, если a[i] положительно, мы должнывсегда включайте его в подпоследовательность, потому что это только увеличит сумму.Эта интуиция соответствует коду

dp[i] = max(dp[i-1], dp[i-1] + a[i])

Так что макс.Сумма проблемы подпоследовательности проста и не требует DP вообще.Проще говоря,

sum = 0
for v in a:
     if  v >0
         sum += v

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

dp[i] = max(dp[i-1]+a[i], a[i])    

Первый термин - это «включить [i] в ​​непрерывный подмассив», а второй - решить начать новуюподмассив, начинающийся с [i].

В этом случае dp[i] является макс.сумма непрерывного подмассива, оканчивающегося на index-i.

Это, безусловно, лучше, чем наивный подход O (n ^ 2) * O (n), к for j in range(0,i): внутри i-цикла и sumвсе возможные подмассивы.

Одна небольшая оговорка, поскольку задан способ dp[0], если все элементы в a отрицательны, мы не выберем ни одного.Таким образом, для непрерывного подмассива с максимальной суммой мы изменим его на

dp[0] = a[0]