Алгоритм Кадана: подмассив с максимальной суммой значений (maximum subarray problem)

Задача. Дан (неотсортированный) массив с числами, нужно найти его непрерывный подмассив так, чтобы сумма чисел была максимальной среди всех возможных других подмассивов.

Пример. Показан на рисунке ниже.

Дан массив {-2, 1, -3, 4, -1, 2, 1, -5, 4}. Его максимальный непрерывыный подмассив выделен желтым маркером и состоит из чисел {4, -1, 2, 1}. Сумма этого подмассива равна 6 и это максимальное значение среди любых других непрерывных подмассивов даввного массива.

Решение в лоб.
Для каждого элемента массива считаем возможные непрерывные подмассивы, которые его содержат.
То есть, начинаем с числа -2. Сумма = -2.
Затем рассамтриваем подмассив {-2, 1}. Сумма = -1.
Затем рассамтриваем подмассив {-2, 1, -3}. Сумма  = -4.
...
Подмассив, который содержит весь массив от -2 до 4 (конец массива).
Это мы обработали число 2.

Теперь стартуем с 1.
Затем рассматриваем {1, -3}.
...
И так далее, пока не дойдём до подмассива от 1 до конца массива.

И так далее.

Нетрудно заметить (нетрудно же?), что сложность этого алгоритма O(n^2).

Как можно сделать быстрее? Динамическое программирование в помощь!

Что такое "динамическое программирование"?

Источник: Как объяснить концепцию динамического программирования 4-летнему ребенку

*записывает"1+1+1+1+1+1+1+1 =" на листе бумаги*
"Чему это равно?"
*считает* "Восемь!"
*дописывает ещё одну "1+" слева*
"А теперь?"
*быстро отвечает* "Девять!"
"Как тебе удалось так быстро подсчитать, что это девять?"
"Просто добавил единичку (к восьми)"
"То есть тебе не пришлось пересчитывать, потому что ты помнил, что там было восемь! Динамическое програраммирование - это красивый способ назвать 'запомнить кое-что, чтобы сэкономить время потом'"

Алгоритм Кадана 
Теперь посмотрим, как выглядел бы наш алгоритм "в лоб", если бы мы считали данные с конца массива. 

Мы берем последний элемент A[n-1] и считаем для него суммы массивов, которые заканчиваются в элеметах A[n-2], A[n-3], ..., A[0], как показано на рисунке:

 
А теперь рассмотрим подробнее элементы A[4]=-1 и A[5]=2. См. рисунок:

Из рисунка выше видно, что local_maximum[4] = 3 и это сумма подмассива [4, -1]. Зная local_maximum[4], нам не нужно подсчитывать суммы всех подмассивов, заканчивающихся в элементе A[5]. Нам достаточно рассмотреть подмассивы, отмеченные красной стрелочкой на рисунке выше, чтобы подсчитать  local_maximum[5].

И это приводит нас к принципу работы алгоритма Кадана.

local_maximum[i] = max(A[i], A[i]+local_maximum[i-1])

Таким образом, для каждого индекса i, задача сводится к тому, чтобы найти максимум ДВУХ чисел: A[i] и A[i]+local_maximum[i-1]. Учтём, что local_maximum[0] = A[0] (потому что на шаге i=0 мы рассматриваем только один элемент A[0]). Кроме того, нам достаточно одного прохода от 1 до A.length, чтобы решить задачу. И это, конечно, гораздо лучше, чем решение "в лоб", рассмотренное выше. Ибо сложность алгоритма в таком случае: O(n).

Имплементация алгоритма на Java:

public static int kadaneValue(int[]matrix) {
        int local_maximum = matrix[0];
        int global_maximum = local_maximum;
       
        for (int i = 1; i < matrix.length; i++) {
            local_maximum = Math.max(matrix[i], matrix[i]+local_maximum);
            if (local_maximum>global_maximum) {
                global_maximum=local_maximum;
            }
        }
        return global_maximum;
    }

Обратите внимание, что вместо подсчёта массива local_maximum[i] мы используем одну переменную local_maximum, которую используем на каждой итерации i. А в переменной global_maximum мы запоминаем наибольшее встретившееся нам значение local_maximum. Итоговое значение global_maximum и будет результатом алгоритма.