Максимальная непрерывная непрерывная подпоследовательность равна нулю?

Question

Я пытаюсь понять решение этой проблемы: «Учитывая последовательность чисел, найдите максимальную сумму смежной подпоследовательности этих чисел». Я привел решение и объяснение ниже.

То, что я не понимаю, в строке «maxendinghere = max (maxendinghere + s, 0)», почему maxendinghere когда-либо будет равна нулю?

def max_sum_subsequence(seq): 
    maxsofar = 0 
    maxendinghere = 0 
    for s in seq: 
     # invariant: maxendinghere and maxsofar are accurate 
     # are accurate up to s 
     maxendinghere = max(maxendinghere + s, 0) 
     maxsofar = max(maxsofar, maxendinghere) 
    return maxsofar 

Объяснение с веб-сайта «Ну, по сути maxendinghere является то, что накопление подпоследовательности -. Он катиться следующий элемент в себя Если эта накопленная сумма никогда не станет отрицательным, мы знаем, что подпоследовательности-который-ends- здесь мы в настоящее время отслеживаем хуже, чем пустая подпоследовательность, которая перезапускает здесь, поэтому мы можем перезагрузить наш аккумулятор подпоследовательности, и первое предложение инварианта цикла все еще сохраняется ».

Что я не понимаю, допустим, моя последовательность 2 -3 4: почему maxendinghere когда-либо будет равна нулю? Нет подпоследовательности, сумма которой равна нулю.

(Цитаты из: http://wordaligned.org/articles/the-maximum-subsequence-problem)

Answer 1

В вашем примере 2 -3 4, спросите себя, что это максимальная сумма, которая заканчивается на индексе 1? 2 - 3 есть -1. -3 сам по себе -3. Таким образом, наша максимальная сумма, то пустая сумма, которая не выбирает нет элементов и, следовательно, имеет сумму 0.

Помните, что пустая подпоследовательность всегда есть возможность, а значение Идентичности sum операции равна 0. Таким образом, например, максимальная сумма смежной подпоследовательности в пределах -2 -4 -3 - это просто 0, сумма пустой подпоследовательности.

Чтобы проверить это:

>>> max_sum_subsequence([-2, -4, -3]) 
0 
>>> sum([]) == 0 
True 

Чтобы изменить алгоритм так, что подпоследовательность должна иметь по крайней мере, длина 1, вы можете сделать это, изменив две строки кода.

Сначала измените инициализацию maxsofar как первый элемент или None, если он не существует. Вместо None вы можете использовать любое значение по умолчанию по вашему выбору. Значение по умолчанию - это то, что возвращается для пустой входной последовательности.

maxsofar = seq and seq[0] or None 

Во-вторых, изменить назначение к maxendinghere, чтобы заставить его включить значение, по меньшей мере, одного элемента из последовательности:

maxendinghere = max(maxendinghere + s, s)