Given that the spoiler time is finished (I think) these are my solutions to the Quiz #131. I only worked on single arrays (and not matrixes). If found 3 different solutions. The first one just searches through the solution space and calculates the value for each subarray. It takes O(n^3). The second one uses that the sum is associative to use the previous calculation for the sum of a subarray to decrese the time complexity to O(n^2). And, in the end, I've found a way to find the max sub array in a single pass O(n). All the solutions have constant space constraints (O(1)). Here is the code (also at http://pastie.caboo.se/78970): #!/usr/bin/env ruby class Array # Runs in O(n^3), change the value function and find using any objective function. def max_subarray_original better_subarray = [] better_value = 0 (0...self.length).each do |start| (start...self.length).each do |finish| value = value(start, finish) if (value > better_value) then better_value = value better_subarray = self[start..finish] end end end better_subarray end def value(start, finish) self[start..finish].inject(0) { |acum, value| acum+value } end # Runs in O(n^2), uses the sum asociativity to avoid an iteration through the array. def max_subarray_optimized better_subarray = [] better_value = 0 (0...self.length).each do |start| value = 0 (start...self.length).each do |finish| value += self[finish] if (value > better_value) then better_value = value better_subarray = self[start..finish] end end end better_subarray end # It's technically imposible to improve it in time or space complexity. # Runs in O(n) time and O(1) space*. # * Assumes that each number takes the same space in memory and that additions, substractions and comparisions take constant time. def max_subarray_single_pass sum = 0 min_pos = -1 min_value = 0 min_pos_at_left = -1 min_value_at_left = 0 better_end_pos = -1 better_value = 0 self.each_with_index do |value, index| sum += value if sum - min_value > better_value then better_value = sum - min_value better_end_pos = index min_value_at_left = min_value min_pos_at_left = min_pos end if sum < min_value then min_value = sum min_pos = index end end return [] if better_end_pos == -1 return self[(min_pos+1)..better_end_pos] end end # some manual testing [[-1, 2, 5, -1, 3, -2, 1], [1, -1000, 100], [-3, -2, -1]].each do |array| puts "array" p array puts "max_subarray_original" p array.max_subarray_original puts "max_subarray_optimized" p array.max_subarray_optimized puts "max_subarray_single_pass" p array.max_subarray_single_pass end

on 2007-07-15 14:36

on 2007-07-15 15:06

On Sun, 15 Jul 2007 21:30:59 +0900, Aureliano Calvo wrote: > Given that the spoiler time is finished (I think) these are my > solutions to the Quiz #131. And here is mine, which I think it's the same of your solution #3. If I understand the problem correctly this is a known problem and finding the optimal solution is a classic example of Dynamic Programming (where programming = planning, no relation with eval & duck typing). But I solved it some time ago with TDD finding an cool case where test-first finds an optimal algorithm, so it may be interesting to report it. Notice that I start finding the maximum subsequence value, well'keep track of the indexes later. #max.rb, step 1. I use variable length arguments instead of array objects. if __FILE__ == $0 require 'test/unit' class TC < Test::Unit::TestCase alias is assert_equal def test_maxseq is 0, maxseq(0) end end end # ok, test fails cause no maxseq exists, yet # step 2 def maxseq(*ary) total=0 end # passes, step 3: def test_maxseq is 0, maxseq(0) is 3, maxseq(0,1,2) end # fails, we need a sum: def maxseq(*ary) total=0 ary.each {|el| total+=el} total end # ok now passes again, try with a negative number: def test_maxseq is 0, maxseq(0) is 3, maxseq(0,1,2) is 0, maxseq(-1), "we choose 0 if we have only negative values" end # return 0 if adding means getting a smaller result def maxseq(*ary) total=0 ary.each {|el| total=[total+el,0].max} total end # ok, passes again, let's add some more complex sequences: is 6, maxseq(1,2,3) is 3, maxseq(1,-2,3) is 3, maxseq(1,2,-3) # mh.. the last fails, because we return 0.. we should keep the current value, which will be zero at the beginning: def maxseq(*args) total=0 current=0 args.each do |el| current=[current+el,0].max total=[total,current].max end total end # now let's throw some more stuff at it: def test_maxseq is 0, maxseq(0) is 3, maxseq(0,1,2) is 0, maxseq(-1), "we choose [] if we have only negative values" is 6, maxseq(1,2,3) is 3, maxseq(1,-2,3) is 3, maxseq(1,2,-3) is 3, maxseq(1,2,-3) is 5, maxseq(-1,2,3) is 0, maxseq(-1,-2) is 8, maxseq(1,-2,3,4,-5,6,-7) is 6, maxseq(1,-2,-3,6) is 11,maxseq(0,1,-2,-3,5,6) end And then you realize.. well, it works, no need for complications, and it runs in linear time, which is pretty good, compared to the naive approach of trying all possible subsequences. Now, to make it a dirty oneliner: def maxseq(*ary) ary.inject([0, 0]) {|(t, c), e| [[t, c=[c+e, 0].max].max, c]}.first end and all tests still pass :) By this point it is trivial to keep track of the indexes: def maxseq_indexes(*args) # total now means "total value, where they start, where they finish" total = start = finish = 0 # current too current = curr_start = curr_finish =0 args.each_with_index do |el,idx| if current+el >= 0 current+=el curr_finish = idx else current = 0 curr_start = idx+1 end if current >= total total = current start = curr_start finish = curr_finish end end total.zero? ? [] : args[start..finish] end and its tests: def test_maxseq_indexes2 is [], maxseq_indexes(0) is [0,1,2], maxseq_indexes(0,1,2) is [], maxseq_indexes(-1), "we choose [] if we have only negative values" is [1,2,3], maxseq_indexes(1,2,3) is [3], maxseq_indexes(1,-2,3) is [1,2], maxseq_indexes(1,2,-3) is [2,3], maxseq_indexes(-1,2,3) is [], maxseq_indexes(-1,-2) is [3,4,-5,6], maxseq_indexes(1,-2,3,4,-5,6,-7) is [6], maxseq_indexes(1,-2,-3,6) is [5,6],maxseq_indexes(0,1,-2,-3,5,6) is [2,5,-1,3], maxseq_indexes(-1, 2, 5, -1, 3, -2, 1) end I'm quite sure it can be made a oneliner again, but I am busy :)

on 2007-07-15 15:40

>>> sender: "Aureliano Calvo" date: "Sun, Jul 15, 2007 at 09:30:59PM +0900" <<<EOQ Hi all, > Given that the spoiler time is finished (I think) these are my > solutions to the Quiz #131. I only worked on single arrays (and not > matrixes). If found 3 different solutions. The first one just searches > through the solution space and calculates the value for each subarray. > It takes O(n^3). The second one uses that the sum is associative to > use the previous calculation for the sum of a subarray to decrese the > time complexity to O(n^2). And, in the end, I've found a way to find > the max sub array in a single pass O(n). The last solution has a bug: $ ruby sol.rb array [-28, -11, -6, -35, 42, 17, 93, -92, -39, 79, -87, -25, -85, 26, 84, 9, 89, -79, 9, 42, -38, 1, -17, -23, 2, -100, -64, 5, 44, -23, -61, 28, -53, 9, 20, -45, -58, 81, -13, -3, 26, -76, 73, -99, -61, 76, -34, -64, -40, 98, 68, -49, -53, -81, -27, 11, 42, 57, 19, 30, -90, 62, 23, -91, -98, -93, 88, -92, -5, -59, -76, 48, -2, 59, -75, -86, -68, 57, 31, 7, -2, 7, 15, 9, -63, 89, -16, 94, -12, -90, -20, -96, -82, -6, -5, 46, 25, -27, 16, 50] max_subarray_original [57, 31, 7, -2, 7, 15, 9, -63, 89, -16, 94] max_subarray_optimized [57, 31, 7, -2, 7, 15, 9, -63, 89, -16, 94] max_subarray_single_pass [] Cheers, Alex

on 2007-07-15 15:57

> $ ruby sol.rb > max_subarray_optimized > [57, 31, 7, -2, 7, 15, 9, -63, 89, -16, 94] > max_subarray_single_pass > [] You're right!!!! It has a bug in the last line :-(. Here is the corrected solution (which passes your test). class Array def max_subarray_single_pass sum = 0 min_pos = -1 min_value = 0 min_pos_at_left = -1 min_value_at_left = 0 better_end_pos = -1 better_value = 0 self.each_with_index do |value, index| sum += value if sum - min_value > better_value then better_value = sum - min_value better_end_pos = index min_value_at_left = min_value min_pos_at_left = min_pos end if sum < min_value then min_value = sum min_pos = index end end return [] if better_end_pos == -1 return self[(min_pos_at_left+1)..better_end_pos] # changed min_pos with min_pos_at_left end end

on 2007-07-15 16:32

On 7/15/07, Aureliano Calvo <aurelianocalvo@gmail.com> wrote: > > $ ruby sol.rb > > max_subarray_optimized > > sum += value > end > > return [] if better_end_pos == -1 > return self[(min_pos_at_left+1)..better_end_pos] # changed min_pos > with min_pos_at_left > end > end > > I've forgotten to tell that the corrected solution is at http://pastie.caboo.se/78975

on 2007-07-15 19:58

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

on 2007-07-15 21:19

Here is a O(n) solution. This simply finds the max accumulation minus the min accumulation. I haven't done too much testing, so I don't know if it handles all of the corner cases. def max_subarray(seq) max_sum = 0 min_sum = 0 max_i = -1 min_i = -1 sum = 0 seq.each_with_index { |val,i| sum += val if sum>max_sum max_sum = sum max_i = i end if sum<min_sum min_sum = sum min_i = i end } if min_i>max_i min_sum = 0 min_i = -1 end seq[(min_i+1)...(max_i+1)] end

on 2007-07-15 22:22

Here's my solution. Nothing fancy. It finds the maximum subarray of the shortest length. class Array def sum inject{ |s,v| s + v } end def subarrays size.times{ |f| 1.upto(size - f){ |l| yield self[f,l] } } end def max_sum results = Hash.new{|h,k| h[k] = [] } subarrays{ |a| results[a.sum] << a } results.max.last.min end end p ARGV.map{ |i| i.to_i }.max_sum if __FILE__ == $PROGRAM_NAME

on 2007-07-16 03:07

On Sunday 15 July 2007 15:18, Eric Mahurin wrote: > Here is a O(n) solution. This simply finds the max accumulation minus > the min accumulation. I haven't done too much testing, so I don't > know if it handles all of the corner cases. > > <snip> FYI, your solution does indeed fail in some cases: irb(main):052:0> arr = [-2,0,0,4,-5,1] => [-2, 0, 0, 4, -5, 1] irb(main):053:0> max_subarray arr => [-2, 0, 0, 4]

on 2007-07-16 04:29

On 7/15/07, Jesse Merriman <jesse.d.merriman@gmail.com> wrote: > => [-2, 0, 0, 4, -5, 1] > irb(main):053:0> max_subarray arr > => [-2, 0, 0, 4] Thanks for pointing out my mistake. I didn't handle the case when the min accumulation comes after the max accumulation very well. Now it records the min index when it finds the best sub-array sum so far (instead of blindly subtracting min from max at the end). Here is a corrected version w/ some testing in irb: def max_subarray(seq) min_sum = 0 min_i = -1 max_delta = 0 max_i = -1 max_i0 = -1 sum = 0 seq.each_with_index { |val,i| sum += val delta = sum-min_sum if delta>max_delta max_delta = delta max_i = i max_i0 = min_i end if sum<min_sum min_sum = sum min_i = i end } seq[(max_i0+1)...(max_i+1)] end irb(main):001:0> require 'quiz131' => true irb(main):002:0> max_subarray([-1, 2, 5, -1, 3, -2, 1]) => [2, 5, -1, 3] irb(main):003:0> max_subarray([-2,0,0,4,-5,1]) => [0, 0, 4] irb(main):004:0> max_subarray([-1, 2, 5, -1, 3, -2, 1]) => [2, 5, -1, 3] irb(main):005:0> max_subarray([31, -41, 59, 26, -53, 58, 97, -93, -23, 84] ) => [59, 26, -53, 58, 97] irb(main):006:0> max_subarray([]) => [] irb(main):007:0> max_subarray([-10] ) => [] irb(main):008:0> max_subarray([10]) => [10] irb(main):009:0> max_subarray([-5, 5]) => [5] irb(main):010:0> max_subarray([5, -5]) => [5]