# Maximum Sub-Array (#131)

**URL:** <https://www.ruby-forum.com/t/maximum-sub-array-131/110267>\
**Category:** Ruby\
**Created:** [July 24, 2007, 7:55pm UTC](https://www.ruby-forum.com/t/maximum-sub-array-131/110267 "2007-07-24T19:55:12Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ivan\_Zdravkovic](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/i/5fc32e/32.png) [@Ivan\_Zdravkovic](https://www.ruby-forum.com/u/Ivan_Zdravkovic)\
**Post date:** [July 24, 2007, 7:55pm UTC](https://www.ruby-forum.com/t/maximum-sub-array-131/110267/1 "2007-07-24T19:55:12Z")

</div>

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)