From: David Tran <email55555@...>
Date: 2007-07-15T22:57:08+09:00
Subject: [Solution] [Quiz] Maximum Sub-Array (#131)

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 )