Алгоритм Кадане

В этом рассказе мы узнаем, как найти максимальную сумму подмассива с помощью алгоритма Кадана. Прежде всего, что такое подмассив?

Подмассив - это непрерывная часть массива. Или массив, находящийся внутри родительского массива. «Сумма подмассива» - это сумма всех элементов подмассива.

Массив длины N будет иметь N * (N + 1) / 2 непустых подмассивов.

Например, предположим, что у нас есть массив [1, 2, -3, 4]. Возможные подмассивы:
[], [1], [2], [-3], [4], [1, 2], [2, - 3], [-3, 4], [1, 2, -3], [2, -3, 4] и [1, 2, -3, 4]
Эти подмассивы будут иметь соответствующие подмассивы,
0, 1, 2, -3, 4, 3, -1, 1, 0, 3, 4
Подмассив с максимальной суммой будет называться Подмассив максимальной суммы.

Обозначим подмассив, содержащий элементы A [i], A [i + 1] …… A [j-1], через A [i, j).

Имея все предпосылки, давайте теперь обсудим алгоритм Кадана, чтобы найти максимальную сумму, которую может иметь подмассив.

Понимание алгоритма Кадане

Рассмотрим массив A длины n. Теперь рассмотрим функцию M (i), которая возвращает максимальную сумму подмассивов среди всех подмассивов, заканчивающихся индексом i, т. Е. A [0, i) , A [1, i), A [i-1, i) или A [i, i) и т. д. Следует отметить, что A [i, i) не будет содержать никаких элементов и, следовательно, это будет пустой подмассив [].

Поскольку все подмассивы A должны заканчиваться на одном из индексов, 0, 1, 2… ..n массива A. Следовательно, максимальная сумма подмассива будет max {M (0), M (1), M (2) …… .M (n)}. Необходимо отметить, что,

подмассивы, заканчивающиеся индексом «i», либо пусты, либо обязательно содержат «A [i-1]».

Получив полную информацию о функции M (i), выведем важное соотношение. Мы знаем,

  1. Подмассивы, заканчивающиеся индексом i: A [0, i), A [1, i), A [2, i) ……… A [i, i) .
  2. M (i) = max {сумма {A [0, i)}, сумма {A [1, i)}, сумма {A [2, i)} …… сумма {A [i-1, i )}, сумма {A [i, i)}}
  3. Или мы можем сказать:
    M (i) = max {max {sum {A [0, i)}, sum {A [1, i)}, …… .sum {A [i- 2, i)} сумма {A [i-1, i)}}, сумма {(A [i, i))}}
  4. Обратите внимание,
    сумма {A [0, i)} = сумма {A [0, i-1)} + A [i-1]
    сумма {A [1, i)} = сумма. {A [1, i-1)} + A [i-1]
    .
    .
    .
    sum {A [i-1, i)} = sum { A [i-1, i-1)} + A [i-1]
  5. Следовательно,
    max {sum {A [0, i)}, sum {A [1, i)}, …… .sum {A [i -1, i)}} =
    max {sum {A [0, i-1)}, sum {A [1, i -1)} ……… сумма {A [i-1, i-1)}} + A [i-1]
  6. Используя шаги 2 и 5,
    max {sum {A [0, i)}, sum {A [1, i)}, …… .sum {A [i-1, i)}} = M ( i-1) + A [i-1]
  7. Подставляя шаг 6 в шаг 3, M (i) = max {M (i-1) + A [i-1], 0}

Слишком много математики? Просто помни это,

M (0) = 0 и M (i) = max {M (i-1) + A [i-1], 0} для 0 ‹i ≤ N.

Имея все M (i), нам просто нужно вычислить их макс. Давайте напишем код, чтобы найти максимальную сумму подмассива, используя алгоритм Кадана.

  1. Создайте две целочисленные переменные: M_i и ans.
  2. Так как M (0) = 0, инициализировать M_i с 0.
    поскольку минимально возможное значение M (i) равно 0, инициализировать ans с 0.
  3. Напишите цикл for для i в диапазоне от 1 до N.
  4. Внутри цикла for напишите
    найдите новый M_i как max (M_i + A [i-1], 0)
    if M_i ›ans, ans = M_i ; // находит максимум из всех M (i)
  5. Конечное значение ans будет максимальной суммой подмассива для данного массива A.