Як знайти підмасив з максимальною сумою (Maximum Subarray Sum) в Ruby

Знайди підмасив з максимальною сумою у масиві чисел за допомогою Kadane’s Algorithm. Просте пояснення, реалізація на Ruby, приклади та тести. Ідеально для тих, хто вивчає алгоритми.

22 трав. '25, 11:01·2 хв. читання

ЗмістНатисність на посилання, щоб перейти до потрібного місця

Умова задачі Принцип розв’язання (Kadane’s Algorithm)Просте пояснення

Розглянемо класичну задачу з алгоритмів: знайти підмасив з максимальною сумою.

Умова задачі

Ми маємо масив цілих чисел (позитивних, негативних або нулі). Потрібно знайти таку неперервну підпослідовність (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) — тобто дуже швидко. Простий для реалізації та тестування.

Програмування