Допустим, вам дан такой массив

-2 1 -3 4 -1 2 1 -5 4

Как узнать самый большой подмассив? При осмотре мы видим, что подмассив

4 -1 2 1

имеет наибольшую сумму, 6.

Как бы вы придумали алгоритм решения этой проблемы? Если вы занимаетесь этим достаточно долго, ваша интуиция подскажет вам динамическое программирование. Вы можете подумать о том, чтобы сделать два цикла, чтобы заполнить половину массива N на N с длинами подмассива от индекса 0 до длины ввода и всего, что между ними. Таким образом, вы можете добавить следующий номер к последнему, чтобы сэкономить время. Что-то вроде этого:

def maxSequence(arr):
 res = hashmap() for i in 0..len(arr)
 for ii in i..len(arr)
 if i == ii: res[i][ii] = arr[i]
 else:
 res[i][ii] = res[i][ii-1] + arr[ii] return max value in res

Обычно вы можете быть удовлетворены этим решением O (n²), но есть нечто, называемое алгоритмом Kadane, который позволяет вам сделать это за O (n) раз.

Вот обоснование.

Вместо сетки N на N мы можем просто использовать линейный размер массива N. В индексе i мы храним подмассив наибольшего возможного размера. Это также то, что мы используем, чтобы решить, включать ли подмассив перед i в следующее значение. Это смущает. Продемонстрируем.

С массивом

-2 1 -3 4

Мы начинаем с

-2

Следующее значение - 1. Если мы хотим включить -2, то подмассив будет -1. Если мы решим опустить -2, тогда подмассив будет 1. 1 больше, чем -1, поэтому мы идем с 1.

-2 1

Далее у нас -3. Если мы решим начать наш подмассив с -3, мы получим -3. Если мы включим лучшее, что было раньше, мы получим -2. Идем с -2. Обратите внимание, что система автоматически отклонила -2, потому что это не помогает.

-2 1 -2

Затем у нас есть 4. Если мы решим опустить все, что было раньше, у нас будет только 4. Если мы выберем лучшее решение из предшествующих 4, мы получим 2. Таким образом, мы решили, что оптимальное решение на данный момент должно начинаться с 4.

Как видите, на каждом этапе оптимальное решение - это максимум в массиве, который мы строим. Завершая этот процесс, получаем

-2 1 -3 4 -1 2 1 -5 4
-2 1 -2 4  3 5 6  1 5

Как и следовало ожидать, оптимальное решение - 6.