On Fri, 13 Jul 2007 23:29:03 +0900, Ruby Quiz 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.

#!/usr/bin/env ruby

require 'matrix'

#strangely, none of these methods are in the facets gem.

module Enumerable
   def argmax 
      curmax=nil
      curval=nil
      each do |x|
	 t=yield x
	 if not curmax or (curmax < t)
	    curmax=t
	    curval=x
	 end
      end
      curval
   end

   def sum
      inject{|a,b|a+b}
   end

   def subarrays
      result=[]
      (0...length).each do |start|
	 ((start + 1)..length).each do |finish|
	    result << self[start...finish]
	 end
      end
      result
   end
end

class Matrix
   include Enumerable
   def submatrices
      result=[]
      (0...row_size).each do |srow|
      (srow+1..row_size).each do |erow|
      (0...column_size).each do |scolumn|
      (scolumn+1..column_size).each do |ecolumn|
	 result << minor(srow...erow,scolumn...ecolumn)
      end end end end
      result
   end
   def each
      (0...row_size).each do |row|
      (0...column_size).each do |column|
	 yield self[row,column]
      end end
   end
end

ARRAY=[-1, 2, 5, -1, 3, -2, 1]
p ARRAY.subarrays.argmax{|x| x.sum}

MATRIX=Matrix[[1,-2,3],[5,2,-4],[5,-5,1]]
p MATRIX.submatrices.argmax{|x| x.sum}


-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/