ЗмістНатисність на посилання, щоб перейти до потрібного місця
Розглянемо класичну задачу з алгоритмів: знайти підмасив з максимальною сумою.
Умова задачі
Ми маємо масив цілих чисел (позитивних, негативних або нулі). Потрібно знайти таку неперервну підпослідовність (subarray), сума якої — максимальна можлива.
max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) # => 6, бо найбільша сума [4, -1, 2, 1]
Важливі моменти:
- Якщо всі числа негативні — повертаємо 0.
- Порожній масив також повертає 0.
- Підмасив має бути неперервним (тобто всі елементи підряд).
Принцип розв’язання (Kadane’s Algorithm)
Ми будемо рухатися по масиву зліва направо, і на кожному кроці:
- Додаємо поточне число до проміжної суми current_sum.
- Якщо current_sum стала меншою за 0 — обнуляємо її.
- Запам’ятовуємо найбільше значення current_sum, яке зустрічалося — це і є наша відповідь.
Якщо сума стала менше 0, вона погіршує наступні значення, тому ми її скидаємо.
Реалізація в Ruby(як і завжди, це один з можливих варіантів реалізації)
def max_sequence(arr)
max_sum = 0
current_sum = 0
arr.each do |n|
current_sum += n
max_sum = [max_sum, current_sum].max
current_sum = 0 if current_sum < 0
end
max_sum
end
Rspec для Ruby методу
RSpec.describe '#max_sequence' do
it 'returns the maximum sum of a contiguous subsequence' do
expect(max_sequence([])).to eq(0)
expect(max_sequence([-1, -2, -3])).to eq(0)
expect(max_sequence([1, 2, 3])).to eq(6)
expect(max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])).to eq(6)
expect(max_sequence([2, -1, 2, 3, 4, -5])).to eq(10)
expect(max_sequence([-2, -3, 4, -1, -2, 1, 5, -3])).to eq(7)
end
end
Просте пояснення
Уявімо, що ми йдемо по масиву і накопичуємо суму. Але якщо в якийсь момент ця сума стала негативною — все, далі вона тільки заважатиме. Ми її скидаємо і пробуємо знову.
Можна уявити, ніби ми шукаємо найвигіднішу ділянку дороги — де набрали найбільше "балів", не дозволяючи втратити все через одну погану яму.
Цей алгоритм підходить для задач типу "знайди найбільшу підпослідовність". Працює за O(n) — тобто дуже швидко. Простий для реалізації та тестування.
