Невозможно понять алгоритм, чтобы найти максимальную сумму Subarray

Question

Я рассматриваю алгоритм, используемый для получения максимальной суммы подматрицы в массиве и не способен понять логику кода. В частности, эта строка max_ending = max(0, max_ending + number). Я не понимаю, что здесь делается. Кроме того, будет этот алгоритм имеет сложность O(n) или O(n^2):

#include <vector> 
#include <algorithm> 
using namespace std; 
template <typename T> T max_sub_array (vector<T> const & numbers) 
{ 
    T max_ending = 0; max_so_far = 0; 
    for(auto & number: numbers) 
    { 
     max_ending = max(0, max_ending + number); 
     max_so_far = max(max_so_far, max_ending); 
    } 
    return max_so_far; 
} 

Спасибо

Answer 1

Алгоритм, который вы представили, кажется, был отнесен (в Wikipedia) к Jay Kadane.Линия, max_ending = max(0, max_ending + number), означает, что мы ищем только неотрицательные суммы; другими словами, если добавление еще одного элемента к текущему подмассиву будет приводить к отрицательной сумме, тогда сделайте максимальную сумму , заканчивающуюся при этом нулевом индексе (т. е. подмашина снова пуста). Строка основывается на идее, что единственный раз, когда нам нужно сбросить окно проверенного субаража, - это если он опускается ниже нуля - даже если большие положительные элементы могут быть добавлены позже, большая сумма субарейма будет достигнута без падения на отрицательный в середине , Давайте посмотрим на примере (max_ending означает максимальную сумму за подмассив, заканчивающийся на текущем индексе):

  {1,2,23,-4,3,-10} 
max_ending 1 3 26 22 25 15 
max_so_far 1 3 26 26 26 26 

Временная сложность для этого алгоритма оцениваются как O(n), так как каждый элемент массива, который должен посетить один раз, а число итераций зависит от размера массива линейным образом. O(n^2) будет означать, что для каждого элемента массива количество итераций будет порядка размера массива; так как размер массива увеличивается, число итераций будет увеличиваться квадратично.

Answer 2

Скажем sum[i] является суммой последовательности заканчиваются numbers[i], то sum[i] = max(numbers[i], numbers[i] + sum[i-1]), ответ max(sum[i] for i from 0 to numbers.size() - 1)

См. Maximum subarray problem

Answer 3

Это взято из упражнения 4.1-5 книги «Введение в алгоритмы». Поскольку этот вопрос и его ответ решают это. Я думаю, что это может быть полезно.

«Используйте следующие идеи для разработки нерекурсивного алгоритма с линейным временем для задачи максимального субарама. Начните с левого конца массива и продвигайтесь вправо, отслеживая максимальный субарак, видимый до сих пор. Зная максимальный подмассиво A [1, j], продолжим ответ, чтобы найти максимальный субаракс, заканчивающийся индексом j + 1, используя следующее наблюдение: максимальный подмассив A [1 .. j + 1] является либо максимальным подрамника A [1 .. j] или подмассива A [i .. j +1], для некоторого 1 < = i < = j + 1. Определить максимальный подмассив формы A [i ... j + 1 ] в постоянное время, основанное на знании максимального подмассива, заканчивающегося индексом j. "

Ответ Сначала мы должны выяснить максимальный вспомогательный массив заканчивая индексом J + 1, который может быть только A [J + 1] или максимальное подмассив заканчивая J плюс A [J + 1], поэтому мы находим максимум этих двух.

После того, как мы получим максимальный вспомогательный массив, заканчивающийся индексом j + 1, мы снова найдем максимум A [1..j + 1], получив максимум между максимальным подвариантом, заканчивающимся индексом j + 1 и максимальным подмассивом A [1..j].

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

Также я думаю, что это неправильно

Edit: Это будет зависеть от определения, если массив не должен содержать, по крайней мере, одно положительное число. В противном случае у вас все в порядке.

max_ending = max(0, max_ending + number); 

должно быть:

max_ending = max(number, max_ending + number); 

max_ending Также и max_so_far должны начинаться с цифр [0] и петли с индексом 1, если вы будете следовать ми изменения.

Сложность для этого алгоритма O (п)

Дополнительное примечание: В вашей версии нет необходимости, чтобы получить максимальное между числом и max_ending + номер, потому что max_ending> = 0, так число < = номер + max_ending