Although totally algorithmic, it sounded like a nice problem. Here is my
solution, based on the explanation in the text which link is given in
the comments. Didn’t test it too much, so don’t rely on it’s
correctness.
Nice day to you all,
Izi
------------------ cut here
Very nice explanation of the various algorithms about this problem:
www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/L02.pdf
by Mordecai J.GOLIN (PhD, Princeton, 1990)
The algorithm below is a Ruby version of the last one,
with additions for the index collecting.
require ‘test/unit’
require ‘test/unit/ui/console/testrunner’
class RQ131
def RQ131.max_sub_array arr
return arr if arr.length < 2
# Current and minimum prefix.
prefix = arr[0]
min_prefix = arr[0] < 0 ? arr[0] : 0
# Maximum sum so far.
max_sum = prefix
# Current candidate and low/high indices.
idx_l_candidate = arr[0] < 0 ? 0 : -1
idx_l = -1
idx_h = 0
for i in 1…arr.length
# New prefix.
prefix += arr[i]
# If the sum is maximal so far, we have new candidate.
if prefix - min_prefix > max_sum
max_sum = prefix - min_prefix
idx_l = idx_l_candidate
idx_h = i
end
# New prefix if lower then current one.
if prefix <= min_prefix
min_prefix = prefix
idx_l_candidate = i
end
end
arr[idx_l + 1…idx_h]
end
end
Some unit tests.
class RQ131Test < Test::Unit::TestCase
def test_max_sub_array1
arr = [-1, 2, 5, -1, 3, -2, 1]
msa = RQ131.max_sub_array arr
assert_equal([2, 5, -1, 3], msa)
end
def test_max_sub_array2
arr = [0, 0, -1, 0, 0, 1]
msa = RQ131.max_sub_array arr
assert_equal([1], msa)
end
def test_max_sub_array3
arr = [-1, -2, -3, -4]
msa = RQ131.max_sub_array arr
assert_equal([-1], msa)
end
def test_max_sub_array4
arr = [1, 2, 3, 4]
msa = RQ131.max_sub_array arr
assert_equal(arr, msa)
end
def test_max_sub_array5
arr = [1, -2, 3, -4, 5, -6, 7, -8]
msa = RQ131.max_sub_array arr
assert_equal([7], msa)
end
def test_max_sub_array6
arr = []
msa = RQ131.max_sub_array arr
assert_equal([], msa)
arr = [1]
msa = RQ131.max_sub_array arr
assert_equal([1], msa)
end
def test_max_sub_array7
arr = [0, 0, 0, 0, 0]
msa = RQ131.max_sub_array arr
assert_equal([0], msa)
end
def test_max_sub_array8
arr = [-1, 2, -3, 4, -5, 6]
msa = RQ131.max_sub_array arr
assert_equal([6], msa)
end
def test_max_sub_array9
arr = [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
msa = RQ131.max_sub_array arr
assert_equal([1, 2, 3, 4, 5], msa)
end
end
Test::Unit::UI::Console::TestRunner.run(RQ131Test)