On Jul 15, 2007, at 7:30 AM, Aureliano Calvo wrote:

> Given that the spoiler time is finished (I think) these are my
> solutions to the Quiz #131.

When I first considered this quiz, I tried to whipped up a quick and  
dirty brute force solution:

#!/usr/bin/env ruby -wKU

array  = [-1, 2, 3, -1, 2]
answer = (0...array.size).inject(Array.new) do |sub_arrs, i|
   sub_arrs.push(*(1..(array.size - i)).map { |j| array[i, j] })
end.map { |sub| [sub.inject(0) { |sum, n| sum + n }, sub] }.max.last

p answer

__END__

I resolved it yesterday using a linear dynamic programming algorithm:

#!/usr/bin/env ruby -wKU

class Array
   def max_subarray
     sum,      start,      length      = self[0], 0,     1
     best_sum, best_start, best_length = sum,     start, length

     each_with_index do |n, i|
       sum, start, length = 0, i, 0 if sum < 0

       sum    += n
       length += 1

       best_sum, best_start, best_length = sum, start, length if sum  
 > best_sum
     end

     self[best_start, best_length]
   end
end

if __FILE__ == $PROGRAM_NAME
   if ARGV.empty?
     require "test/unit"

     class TestMaxSubarray < Test::Unit::TestCase
       def test_single_element
         -1.upto(1) { |n| assert_equal(Array(n), Array 
(n).max_subarray) }
       end

       def test_all_positive
         assert_equal([1, 2, 3], [1, 2, 3].max_subarray)
       end

       def test_all_negative
         assert_equal([-1], [-3, -2, -1].max_subarray)
       end

       def test_quiz_example
         assert_equal([2, 5, -1, 3], [-1, 2, 5, -1, 3, -2,  
1].max_subarray)
       end
     end
   else
     p ARGV.map { |n| Integer(n) }.max_subarray
   end
end

__END__

James Edward Gray II