From: Matthew Rudy <matthewrudyjacobs@...>
Date: 2007-07-18T18:06:33+09:00
Subject: Re: Maximum Sub-Array (#131)

this is my first entry
(only found this place last week)

so it's late,
but I like it.

I deal with left-subarrays, and right-subarrays
(i decided that intuitively a max sub array is a max left of a max 
right,
but have not the time to prove this)
I also assume that the empty array [] is always a member.

also, my max_left_of_right and max_right_of_left methods will return 
multiple copies of the empty array if that is indeed the smallest.

I did initially uniq the result,
but decided against it in the end
(who says that the empty array is a unique sub array -- probably me)

class Array

  # solution 1
  def max_subs
    max_found, max_instances = 0, [[]]  # the empty sub array will 
always return 0 sum
    self.left_subs.each do |l_sub|
      next if l_sub.last.nil? || l_sub.last < 0   # if
      l_sub.right_subs.each do |sub|
        next if sub.first.nil? || sub.first < 0
        if (sub_sum = sub.sum) > max_found
          max_found, max_instances = sub_sum, [sub]
        elsif sub_sum == max_found
          max_instances << sub
        end
      end
    end
    return max_instances
  end

  # i hypothesise that each max sub array is actually;
  # a max left sub of a max right sub, and the other way round
  # but i dont have time to prove it

  # solutions 2 and 3
  def max_left_of_right
      max_right_subs.inject([]){|rtn, max_r| rtn + max_r.max_left_subs}
  end

  def max_right_of_left
      max_left_subs.inject([]){|rtn, max_l| rtn + max_l.max_right_subs}
  end


  # sub methods

  def left_subs
    if (l_sub = self.dup) && l_sub.pop
      return (l_sub.left_subs << self.dup)
    else
      return [self]
  end
  end

  def right_subs
    if (r_sub = self.dup) && r_sub.shift
      return (r_sub.right_subs << self.dup)
    else
      return [self]
  end
  end

  def sum
    self.inject(0){|sum, element| sum+element}
  end

  def max_left_subs
    max_of_subs(:left_subs)
  end

  def max_right_subs
    max_of_subs(:right_subs)
  end

  def max_of_subs(method)
    max_found, max_instances = 0, [[]] # we expect to have an empty sub
    self.send(method).each do |sub|
      if (sub_sum = sub.sum) > max_found
        max_found, max_instances = sub_sum, [sub]
      elsif sub_sum == max_found
        max_instances << sub
      end
    end
    return max_instances
  end
end

-- 
Posted via http://www.ruby-forum.com/.