From: Carl Porth <badcarl@...>
Date: 2007-07-16T00:55:05+09:00
Subject: Re: Maximum Sub-Array (#131)

#!/usr/bin/env ruby

require "rubygems"
require "facets"
require "enumerable/each_unique_pair"
require "enumerable/sum"

class Array
  # all contiguous subarrays
  def sub_arrays
    [*0..self.size].to_enum(:each_unique_pair).map { |a,b|
self[a..b-1] }
  end
end

array = [-1, 2, 5, -1, 3, -2, 1]

# I find this easy on the eyes
array.sub_arrays.max { |a,b| a.sum <=> b.sum } # => [2, 5, -1, 3]

# but if you didn't want to recompute the sums you could do this
array.sub_arrays.map { |a| [a.sum,a] }.max.last # => [2, 5, -1, 3]


On Jul 13, 7:29 am, Ruby Quiz <ja...@grayproductions.net> wrote:
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz message,
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=
>
> by Harlan
>
> Given an array of integers, find the sub-array with maximum sum.  For example:
>
>         array:              [-1, 2, 5, -1, 3, -2, 1]
>         maximum sub-array:  [2, 5, -1, 3]
>
> Extra Credit:
>
> Given a matrix of integers, find the rectangle with maximum sum.