Table of contentsClick link to navigate to the desired location
This content has been automatically translated from Ukrainian.
Let's consider a classic algorithmic problem: find the subarray with the maximum sum.
Problem Statement
We have an array of integers (positive, negative, or zeros). We need to find a contiguous subsequence (subarray) whose sum is the maximum possible.
max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) # => 6, because the largest sum is [4, -1, 2, 1]
Important points:
- If all numbers are negative — return 0.
- An empty array also returns 0.
- The subarray must be contiguous (i.e., all elements in a row).
Solution Principle (Kadane’s Algorithm)
We will move through the array from left to right, and at each step:
- Add the current number to the temporary sum current_sum.
- If current_sum becomes less than 0 — reset it to 0.
- Remember the largest value of current_sum encountered — this is our answer.
If the sum becomes less than 0, it worsens the subsequent values, so we reset it.
Implementation in Ruby(as always, this is one of the possible implementations)
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 for Ruby method
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
Simple Explanation
Imagine that we are going through the array and accumulating the sum. But if at some point this sum becomes negative — that's it, it will only hinder us further. We reset it and try again.
One can imagine that we are looking for the most profitable section of the road — where we scored the most "points," without allowing everything to be lost due to one bad pit.
This algorithm is suitable for "find the largest subsequence" type problems. It works in O(n) — that is, very quickly. Simple to implement and test.
This post doesn't have any additions from the author yet.
