Алгоритм Кадане – максимальна підпослідовність

Повне пояснення

Коротке пояснення

Алгоритм Кадане шукає підмасив з найвищою сумою в заданому масиві. Він працює, додаючи кожен елемент до поточної суми і порівнюючи її з максимумом, а коли сума стає від’ємною – скидає її до нуля.

Аналогія

Уявіть, що ви йдете по схилу: кроки – це елементи масиву, а накопичена сума – ваш підйом. Якщо ви падаєте (сума стає від’ємною), ви знову починаєте підйом з нуля.

Коли застосовувати

• Пошук максимальної суми підмасиву у числовому масиві.
• Дані можуть бути як позитивними, так і негативними числами.
• Потрібен однопрохідний розв’язок без підмасивів.
• Не потрібна конкретна позиція підмасиву, лише її сума.

Кроки алгоритму

1. Ініціалізувати currentSum і maxSum як перший елемент масиву.
2. Для кожного наступного елемента x:
   • Обчислити нову суму: currentSum = Math.max(x, currentSum + x).
   • Оновити максимум: maxSum = Math.max(maxSum, currentSum).
3. Повернути maxSum як результат.

Візуальна інтуїція (текстова)

Масив: [−2, 1, −3, 4, −1, 2, 1, −5, 4]

Крок | x | currentSum | maxSum
-----|---|------------|-------
1    |−2 | −2         | −2
2    | 1 | 1          | 1
3    |−3 | −2         | 1
4    | 4 | 4          | 4
5    |-1 | 3          | 4
6    | 2 | 5          | 5
7    | 1 | 6          | 6
8    |-5 | 1          | 6
9    | 4 | 5          | 6

Складність

• Часова складність: O(n) – один прохід по масиву.
• Пам’ятна складність: O(1) – лише кілька змінних.
• Найгірший випадок: коли всі числа негативні, алгоритм все одно працює за O(n).

Код (js)

// Функція, що повертає максимальну суму підмасиву за алгоритмом Кадане
function kadaneMaxSubarraySum(arr) {
  // Перевірка на порожній масив
  if (arr.length === 0) return 0;

  // Ініціалізуємо поточну суму і максимум як перший елемент
  let currentSum = arr[0]; // накопичувальна сума, що розглядається
  let maxSum = arr[0];     // найвища знайдена сума підмасиву

  // Проходимо по масиву, починаючи з другого елемента
  for (let i = 1; i < arr.length; i++) {
    const x = arr[i];

    // Якщо додавання поточного елемента до currentSum робить його меншим за самий елемент,
    // краще почати новий підмасив з цього елемента
    currentSum = Math.max(x, currentSum + x);

    // Оновлюємо максимум, якщо нова поточна сума більша
    maxSum = Math.max(maxSum, currentSum);
  }

  // Повертаємо знайдену максимальну суму підмасиву
  return maxSum;
}

// Тестовий приклад
console.log(kadaneMaxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // очікуваний результат: 6

Типові помилки і поради

1. Не обробляти порожній масив – це призведе до помилки доступу до arr[0].
2. Забувати скинути currentSum, коли він стає від’ємним – алгоритм не працюватиме для всіх негативних чисел.
3. Використовувати for...of без індексу – важко отримати попередню суму.
4. Не зберігати максимум – можна втративши найкращий підмасив.
5. Оптимізація: якщо потрібна позиція підмасиву, можна зберігати індекси початку і кінця.

Перевір себе

1. Що робить currentSum = Math.max(x, currentSum + x)?
2. Яка складність пам’яті алгоритму Кадане?