# [QUIZ-Solution] Maximum Sub-Array (#131)

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)

---------------------------------
Sick sense of humor? Visit Yahoo! TV's Comedy with an Edge to see what's on, when.