# \[Quiz\] Maximum Sub-Array (#131)

**URL:** <https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109474>\
**Category:** Ruby\
**Created:** [July 15, 2007, 3:58pm UTC](https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109474 "2007-07-15T15:58:45Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [July 15, 2007, 3:58pm UTC](https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109474/1 "2007-07-15T15:58:45Z")

</div>

Email sender may warp golf code to invalid code, please reference my  
blog for solution.

# My solution for Ruby Q. - Maximum Sub-Array (#131) -

[http://www.rubyquiz.com/quiz131.html](http://www.rubyquiz.com/quiz131.html)

# Blog : [http://davidtran.doublegifts.com/blog/?p=89](http://davidtran.doublegifts.com/blog/?p=89)

# Quiz : Given an array of integers, find the sub-array with maximum

sum.

# Notes :

# (1) max\_sub finds a solution. (golf code)

# 

# (2) max\_sub2 finds the shortest of sub-arrays which all have the

same maximum sum.

# 

# (3) max\_sub3 finds a solution with complexity ~ Theta (n \* log n).

# The reference is:

> **[L02.pdf](https://cse.hkust.edu.hk/faculty/golin/COMP271Sp03/Notes/L02.pdf)**
>
> 69.75 KB

# It implements the Divide-and-Conquer solution base on reference

paper page 6~9.

def max\_sub(a)  
a[(0…(n=a.size)).inject([]){|r,i|(i…n).inject(r){|r,j|r\<\<(i…j)}}.sort\_by{|r|a[r].inject{|i,j|i+j}}[-1]]  
end

def max\_sub2(ary)  
return ary if ary.size \<= 0

n = ary.size - 1

range = (0…n).inject([]) do |a, i|  
(i…n).inject(a) { |a, j| a \<\< (i … j) }  
end.sort\_by do |r|  
[ary[r].inject { |a, b| a + b }, # sum of sub array; if sum are  
equal,  
r.begin - r.end # we want the shortest of sub  
arrays.  
]  
end.last

ary[range]  
end

#=============================================================================#

def max\_sub\_array\_from\_begin(ary) # max sub-array contains first element  
index = 0  
max = ary[index]  
sum = 0  
ary.each\_with\_index do |e, i|  
sum += e  
if sum \> max  
max = sum  
index = i  
end  
end  
[0…index, max]  
end

def max\_sub\_array\_from\_end(ary) # max sub-array contains last element  
r, max = max\_sub\_array\_from\_begin(ary.reverse) # maybe slow because  
reverse…  
[(ary.size - 1 - r.end) … (ary.size - 1), max]  
end

def mcs\_middle(ary, i, j)  
pivot = (i+j) / 2 + 1  
r1, max1 = max\_sub\_array\_from\_end(ary[i…pivot])  
r2, max2 = max\_sub\_array\_from\_begin(ary[pivot…j])  
[r1.begin … (pivot + r2.end), max1 + max2]  
end

def mcs(ary, i, j)  
return (i…j) if i == j  
r1 = mcs(ary, i, (i+j)/2)  
r2 = mcs(ary, (i+j)/2+1, j)  
s1 = ary[r1].inject{|a,b|a+b}  
s2 = ary[r2].inject{|a,b|a+b}  
r3, s3 = mcs\_middle(ary, i, j)  
if s1 \> s2  
(s3 \> s1) ? r3 : r1  
else  
(s3 \> s2) ? r3 : r2  
end  
end

def max\_sub3(ary)  
return ary if ary.size \<= 0  
ary[mcs(ary, 0, ary.size - 1)]  
end

# some tests …

a1 = [-1, 2, 5, -1, 3, -2, 1]  
a2 = [-50, 6, -20, 1, 2, 3, -7]  
p max\_sub( a1 )  
p max\_sub( a1 )  
p max\_sub2( a2 )  
p max\_sub3( a1 )  
p max\_sub3( a2 )