Table of contentsClick link to navigate to the desired location
This content has been automatically translated from Ukrainian.
Let's consider a classic problem from algorithms: 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 interim 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 the 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.
You can think of it as searching for the most profitable stretch of road — where we gained the most "points," without allowing one bad pit to make us lose everything.
This algorithm is suitable for problems like "find the largest subsequence." It works in O(n) — meaning it's very fast. Simple to implement and test.
This post doesn't have any additions from the author yet.
