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

[David Tran]

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

# My solution for Ruby Quiz - Maximum Sub-Array (#131) -
http://www.rubyquiz.com/quiz131.html
# Blog : 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:
http://www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/L02.pdf
# 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 )