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.

on 2007-07-13 16:35

on 2007-07-13 16:49

> > 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] Just to confirm the problem. Wouldn't the maximum sub array be [2, 5, 3] ? Matt

on 2007-07-13 16:51

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote: > > > Just to confirm the problem. Wouldn't the maximum sub array be > > [2, 5, 3] ? > Duh. Nevermind :) Maximum sub *array*. I get it. Carry on. Don't mind me... Matt

on 2007-07-13 17:58

On Jul 13, 10:29 am, Ruby Quiz <ja...@grayproductions.net> wrote: > > 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. Nice quiz. One question. For an array containing all negative integers, is the maximimum sub- array an empty array or a single-value array containing the highest value? For example: array: [-1,-2,-3] maximum sub-array: [] or [-1] ? Regards, Paul.

on 2007-07-13 18:29

On Jul 13, 2007, at 10:42 AM, Paul Novak wrote: >> >> >> Given a matrix of integers, find the rectangle with maximum sum. > > maximum sub-array: [] > or [-1] ? Let's say we are looking for a non-empty subarray. James Edward Gray II

on 2007-07-13 18:46

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote: > On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote: > > > 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] What are the criteria for selecting from multiple possibilities? For example: [1,2,3,-7,6] options: [1,2,3] [6] Does it matter?

on 2007-07-15 16:40

> > Given a matrix of integers, find the rectangle with maximum sum. > > # # Here is my solution. # If there are multiple sub arrays that equal max sum, it prints all of them. require 'enumerator' arr, s = [1,5,3,-9,9], [] (1..arr.length).each{|q| arr.each_cons(q) {|x| s << x}} big = s.max {|x,y| x.inject(0) {|a,b| a+b} <=> y.inject(0) {|c,d| c+d}} p s.select {|r| r.inject(0) {|a,b| a+b} == big.inject(0) {|c,d| c+d}} # Harry

on 2007-07-15 16:42

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

on 2007-07-15 16:48

Ruby Quiz wrote: > > Given a matrix of integers, find the rectangle with maximum sum. > > *# The algorithm for max_subarray is a slightly adapted version of # the linear solution presented in # "Programming pearls: algorithm design techniques" # by Jon Bentley, published in Communications of the ACM, # volume 27, Issue 9 (september 1984). According to the article, it # was designed by Jay Kadane (in less than a minute) in 1977. # The algorithm for max_submatrix was inspired by some of the ideas in the same # article and large quantities of coffee. # Running time: O(n) def max_subarray(arr) if (max = arr.max) <= 0 # if all the numbers in the array are less than or equal to zero, # then the maximum subarray is simply the array # consisting of the largest value max_idx = arr.index(max) return max, max_idx, max_idx end # starting index of the maximum subarray x1 = 0 # ending index of the maximum subarray x2 = 0 # the maximum value found so far running_max = 0 # the maximum value of the array ending on the current # value (in the block below) or zero, if the maximum # array becomes negative by including the current value max_ending_here = 0 # the start index of a possible maximum subarray start_idx = 0 arr.each_with_index do |i, idx| start_idx = idx if max_ending_here == 0 max_ending_here = [0, max_ending_here + i].max if max_ending_here > running_max running_max = max_ending_here x1 = start_idx x2 = idx end end return running_max, x1, x2 end # Running time: O(m^2 * n) def max_submatrix(matrix) # We already have a nice linear algorithm for solving # the problem in one dimension. What we want to do is # basically to reduce the problem to an array, and then # solve that problem using max_subarray. # The problem can be solved this way for any contiguous # number of rows by simply adding them together, thereby # "collapsing" them into one row, and then going from there. # Now, we want to do this efficiently, so we create # a cumulative matrix, by adding the elements of the columns # together. That way, we only need to look up one value # pr. column to get the sums of the columns in any sub matrix. c_matrix = matrix.inject([]) do |memo, arr| prev_arr = memo.last memo << (prev_arr == nil ? arr : Array.new(arr.size) { |i| prev_arr[i] + arr[i] }) end # the maximum value found so far running_max = 0 # starting index of the horizontal maximum subarray x1 = 0 # ending index of the horizontal maximum subarray x2 = 0 # starting index of the vertical maximum subarray y1 = 0 # ending index of the vertical maximum subarray y2 = 0 c_matrix.each_with_index do |c_arr, vert_iter_end| 0.upto(vert_iter_end) do |vert_iter_start| arr = c_arr if vert_iter_start != vert_iter_end arr = Array.new(c_arr.size) { |i| c_arr[i] - c_matrix[vert_iter_start][i] } end c_max, hz_s, hz_e = max_subarray(arr) if c_max > running_max running_max = c_max x1, x2, y2 = hz_s, hz_e, vert_iter_end y1 = vert_iter_start == vert_iter_end ? 0 : vert_iter_start + 1 end end end return running_max, x1, x2, y1, y2 end array = [-1, 2, 5, -1, 3, -2, 1] max, x1, x2 = max_subarray(array) puts "Maximum subarray for #{array.inspect}: #{array.values_at(x1..x2).inspect}, sum: #{max}" matrix = [ [ 1, 5, -3, 4], [-8, 2, 9, 12], [ 6, 1, -2, 2], [-3, -15, 7, -6] ] max, x1, x2, y1, y2 = max_submatrix(matrix) max_matrix = matrix.values_at(y1..y2).collect { |arr| arr.values_at(x1..x2) } puts "Maximum submatrix for #{matrix.inspect}: #{max_matrix.inspect}, sum: #{max}" *

on 2007-07-15 16:50

I went for the all-in-one line solution (not including the method definition boilerplate), with no consideration for the computational or memory cost. Here are two versons, the first does not require the 'enumerator' library, the second does and is slightly shorter as a result. Both will favor shorter solutions over longer solutions if they have the same sum. In both cases the code generates every possible sub-array and sorts them by two factors: 1) sum of elements ascending, and 2) size of sub- array descending. Finally it chooses the solution at the end of this sorted list. In the first solution, it generates every sub-array by using all possible combinations of starting and ending indices. def max_sub_array(a) (0...a.size).inject([]) { |c, s| c + (s...a.size).map { |e| a.slice(s..e) } }.sort_by { |b| [b.inject { |s, e| s + e }, - b.size] }.last end In the second solution, it generates every sub-array by sequencing through all possible sub-array lengths (1..size) and then calling enum_cons. If you're not familiar with enum_cons, it takes a size as a parameter and returns an Enumerable for every sub-array of that size (e.g., [1, 2, 3, 4].enum_cons(2) would provide an Enumerable that would encode the sequence [1, 2], [2, 3], and [3, 4]). def max_sub_array2(a) (1..a.size).inject([]) { |l, s| l + a.enum_cons(s).to_a }.sort_by { | b| [b.inject { |s, e| s + e }, -b.size] }.last end Eric ==== Are you interested in on-site Ruby training that uses well-designed, real-world, hands-on exercises? http://LearnRuby.com

on 2007-07-15 17:32

Hi all, Here's my solution. It has no other merits than showing me that I really need to get back to studying algorythms more in depth :-) as it's quite slow (needs about 2 minutes for an 1000 elements array). There are just two optimisations I came up with: drop sub arrays starting or ending with negative numbers and breaking out of loop when the sum of the positive numbers left is smaller than the maximum we already have. Cheers, Alex

on 2007-07-15 17:34

On 7/13/07, Ruby Quiz <james@grayproductions.net> wrote: > > Extra Credit: > > Given a matrix of integers, find the rectangle with maximum sum. > > # # Here is my matrix solution. # It does the Matrix extra credit. # If there are multiple rectangles that equal max sum, it prints all of them. # # Since the quiz did not specify how to input, # I just hard coded a sample Matrix at the beginning. # require 'matrix' mat = Matrix[[77,-1,2,3,-4],[-7,8,-22,10,11],[3,15,16,17,-18],[4,22,-23,-24,-25]] s = [] (0...mat.row_size).each do |a| (0...mat.column_size).each do |b| (1..mat.row_size).each do |x| (1..mat.column_size).each do |y| s << mat.minor(a,x,b,y) end end end end tot = s.uniq.map {|x| x.to_a} big = tot.max{|x,y| x.flatten.inject(0) {|a,b| a+b} <=> y.flatten.inject(0) {|c,d| c+d}} subs = tot.select {|r| r.flatten.inject(0) {|a,b| a+b} == big.flatten.inject(0) {|c,d| c+d}} puts "Original Matrix" (0...mat.row_size).each do |x| print mat.row(x).to_a.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n" end puts puts "Solutions" subs.each do |x| puts x.each {|y| print y.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"} end # Harry

on 2007-07-15 17:46

My solution to Quiz 131. It does a straight-forward O(N**2) search. I did add a constraint: the algorithm should return a sub-array of minimal length. This is because I strongly prefer [0] to [0, 0, 0, 0, 0, 0, 0]. My submission also shows my preference for code that is readable/ maintainable rather than golfed/obfuscated. (This is not intended as a shot at those who enjoy code golf -- I'm just saying it's not for me.) <code> # Return the non-empty sub-array of minimal length that maximizes the sum # of its elements. def max_sub_array(arry) max_sum = arry.inject { |sum, n| sum += n } min_length = arry.size result = arry (1...arry.size).each do |i| (i...arry.size).each do |j| sub = arry[i..j] sum = sub.inject { |sum, n| sum += n } next if sum < max_sum next if sum == max_sum && sub.size >= min_length max_sum, min_length, result = sum, sub.size, sub end end result end </code> Regards, Morton

on 2007-07-15 17:47

I didn't try any golfing, but here are 3 attempts. The first and second are straightforward approaches, their only difference is that the second prefers shorter arrays. Both are (n**2 + n) / 2. The third is my clever solution. I think it should have lower complexity (if still a factor of n**2), despite having much more setup code, but I'm not sure what it is exactly. Here's a copy of the main descriptive comment I put in the code: # Try to be clever. First, remove any leading or trailing non-positive numbers, # since including them can only lower the sum. Then, split the array up into # "islands" of same-sign numbers. Zeros will be including in the group to their # left. Map each island to its sum to get an array of alternating +,-,+,-,...,+ # numbers. This is really the fundamental form of an instance of the problem. # It could be run though another max-subarray algorithm, but instead I tried # to take advantage of its structure by only looking at even-number indices. # Then just find the maximum subarray's indices, and map back to the originali # array. An example in case thats not clear enough: Start with: [-1, 0, 2, 4, -1, 5, 0, 6, -2] Trim ends: [2, 4, -1, 5, 0, 6] Sign switches: [0, 2, 3] Islands: [[2, 4], [-1], [5, 0, 6]] new_arr: [6, -1, 11] Try each index pair: [0, 0], [0, 2], [2, 2] Best is: [0, 2] Map back: [2 4 -1 5 0 6] Only 3 index pairs were tested, as opposed to (9**2 + 9)/ 2 = 45 for the others.

on 2007-07-15 17:55

#!/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 2007-07-15 17:57

Just like many others, I went for brute force with some readability. Golf solution at the bottom. class Array def sum inject {|sum, elem| sum + elem} end def sub_arrays subs = [] 0.upto(size-1) { |i| i.upto(size-1) { |j| subs << self[i..j] } } subs end end foo = Array.new(42) { rand(42) - 21 } # build array; choice of numbers here is arbitrary p foo << "\n" # show the array # now show maximum sub-array ... p foo.sub_arrays.inject([foo.max]) { |max, elem| elem.sum > max.sum ? elem : max } Golf solution (3 lines, 120 chars not including array initialization). I'm sure it could be shorter, though :( a = Array.new(42){rand(42)-21} v=[] 0.upto(b=a.size-1){|i|i.upto(b){|j|v<<a[i..j]}} p v.inject([a.max]){|z,m|z.inject{|s,i|s+i}>m.inject{|s,i|s+i}?z:m} Todd

on 2007-07-15 19:48

Morton Goldberg wrote, On 7/15/2007 10:44 AM: > <code> > Doesn't this basically make it order n cubed?

on 2007-07-15 23:05

No extra credit on this one, but my solution handles a regular list of numbers just fine. First, I created an object to define a range of numbers: # Object defining a sub-array of integer values # The sub-array contains a start and end index # defining a region of the master array class SubArray def initialize @start = 0 @end = 0 @sum = 0 end # Set boundaries of the sub-array def set_bounds(list_start, list_end) @start, @end = list_start, list_end end # Provide get/set accessors attr_reader :start, :end, :sum attr_writer :sum end Then I created a class to find the sub-array with the maximum sum. Basically it performs a single pass of the array, updating the maximum sub-array each time the current sum exceeds the current maximum sum: class MaxSubArray # Finds the sub-array with the largest sum # Input: a list of integers def find(list) max = SubArray.new cur = SubArray.new for i in 0...list.size cur.sum = cur.sum + list[i] if (cur.sum > max.sum) max.sum = cur.sum cur.set_bounds(cur.start, i) max.set_bounds(cur.start, i) elsif (cur.sum < 0) # If sum goes negative, this region cannot have the max sum cur.sum = 0 cur.set_bounds(i + 1, i + 1) end end list.slice(max.start, max.end - max.start + 1) end end And finally, here are some tests: $:.unshift File.join(File.dirname(__FILE__), "..") require 'test/unit' require 'max_sub_array.rb' class TestMaxSubArray < Test::Unit::TestCase def setup @ma = MaxSubArray.new end def test_max_sub_array assert_equal([2, 5, -1, 3], @ma.find([-1, 2, 5, -1, 3, -2, 1])) assert_equal([10], @ma.find([-1, 2, 5, -1, 3, -2, -12, 10])) assert_equal(@ma.find([-25, 81, -14, 43, -23, 86, -65, 48]), [81, -14, 43, -23, 86]) assert_equal([9, 11, 23, -5, 15, 18, 6, -18, 21, -4, -17, -19, -10, -9, 19, 17, 24, 10, 21, -23, -25, 21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18, -22, -6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6, 10, 4, 2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23], @ma.find([-16, -8, 9, 11, 23, -5, 15, 18, 6, -18, 21, -4, -17, -19, -10, -9, 19, 17, 24, 10, 21, -23, -25, 21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18, -22, -6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6, 10, 4, 2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23, -23, 16, -19, -10, 12, -17, -9, 6, -8, -23, 16, -17, -10, 24, -1, -6, -24, -5, 16, -11, -7, -8, 12, -21, -23, -8, -8, 4, 7, 6, -22, -8, -19, -7, 23, 4, 9, -19, -19, 0, -15])) assert_equal([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26, 9, 30, 31, 16, 44, 20, 10, 55, 28, -18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17, 38, -5, -28, 45, -38, 4, 4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32, -22, 8, 37, 57, 13, 17, -17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24, 34, -10, -26, -27, 12, 5, -2, 4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56, 10, -35, -29, 40, -1, 30, 45, 36], @ma.find([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26, 9, 30, 31, 16, 44, 20, 10, 55, 28, -18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17, 38, -5, -28, 45, -38, 4, 4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32, -22, 8, 37, 57, 13, 17, -17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24, 34, -10, -26, -27, 12, 5, -2, 4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56, 10, -35, -29, 40, -1, 30, 45, 36, -38, 30, -28])) end end Thanks, Justin

on 2007-07-15 23:22

Here's a solution which iterates over the array just once. Looks like I came up with a variant of the algorithm presented by Henrik Schmidt- Møller, though I'm storing the local max sub array rather than just its delimiting indices. I'm not happy with the calls to slice (especially as they require calculating the size of the array), but I'm pleased that I came up with a solution using recursion. class Array def max_sub_array self.max_sub_arrayr[0] end def max_sub_arrayr ary = self.clone sub_ary = Array.new.push(ary.shift) sum = sub_ary[0] max_sub_ary = sub_ary.dup max_sum = sum done = false ary.each_with_index do |n,i| if sum > 0 if sum + n > 0 sum += n sub_ary.push(n) else sub_ary, sum = ary.slice(i+1..(ary.size-1)).max_sub_arrayr done = true end elsif sum <= n sub_ary, sum = ary.slice(i..(ary.size-1)).max_sub_arrayr done = true end if sum > max_sum max_sum = sum max_sub_ary = sub_ary.dup break if done end end return max_sub_ary, max_sum end end Michael Glaesemann grzm seespotcode net

on 2007-07-16 02:07

I see I was not the only one to borrow inspiration from Programming Pearls. This is O(N) code... some few examples included for testing: def max_subarray_last_index(arr) a = b = x = 0 arr.each_with_index do |e, i| b = [b + e, 0].max unless a > b a, x = b, i end end return x end def max_subarray(arr) i = arr.size - max_subarray_last_index(arr.reverse) - 1 j = max_subarray_last_index(arr) return arr[i..j] end p max_subarray( [-1, 2, 5, -1, 3, -2, 1] ) p max_subarray( [31, -41, 59, 26, -53, 58, 97, -93, -23, 84] ) p max_subarray( [] ) p max_subarray( [-10] ) p max_subarray( [10] ) p max_subarray( [-5, 5] ) p max_subarray( [5, -5] )

on 2007-07-16 03:09

On Jul 15, 2007, at 1:47 PM, Sammy Larbi wrote: >> >> sub = arry[i..j] >> result >> end >> </code> Yes, the inject introduces another factor of N. I missed that. Regards, Morton

on 2007-07-16 03:20

On Sunday 15 July 2007 17:17, Michael Glaesemann wrote: > Here's a solution which iterates over the array just once. Looks like > I came up with a variant of the algorithm presented by Henrik Schmidt- > Møller, though I'm storing the local max sub array rather than just > its delimiting indices. I'm not happy with the calls to slice > (especially as they require calculating the size of the array), but > I'm pleased that I came up with a solution using recursion. > > <snip> Not to be the downer who points out everyone's problems, but here's a bug: irb(main):008:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19, -36, -6, -20, -4, -23, -25, 48, -22, 22, 5, -21, -33, 37, 39, -22, 11, -44, -40, -37, -26] irb(main):009:0> arr.max_sub_array => [37, 39, 10] That sequence does not appear in arr.

on 2007-07-16 05:00

On Jul 15, 2007, at 20:19 , Jesse Merriman wrote: > Not to be the downer who points out everyone's problems, but here's > a bug: No problem at all! Thanks for taking a look at my work :) > irb(main):008:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, > -19, -36, -6, > -20, -4, -23, -25, 48, -22, 22, 5, -21, -33, > 37, 39, > -22, 11, -44, -40, -37, -26] > irb(main):009:0> arr.max_sub_array > => [37, 39, 10] This should be a bit more pleasing :) irb(main):002:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19, -36, -6, -20, -4, -23, -25, 48, -22, 22, 5, -21, -33, 37, 39, -22, 11, -44, -40, -37, -26] irb(main):005:0> arr.max_sub_array => [46, -8, 43] Updated code follows below signature: Michael Glaesemann grzm seespotcode net class Array def max_sub_array return [] if self.empty? self.max_sub_arrayr[0] end def max_sub_arrayr ary = self.clone sub_ary = Array.new.push(ary.shift) sum = sub_ary[0] max_sub_ary = sub_ary.dup max_sum = sum done = false ary.each_with_index do |n,i| if sum > 0 if sum + n > 0 sum += n sub_ary.push(n) else sub_ary, sum = ary.dup.slice(i..(ary.size-1)).max_sub_arrayr done = true end elsif sum <= n sub_ary, sum = ary.dup.slice(i..(ary.size-1)).max_sub_arrayr done = true end if sum > max_sum max_sum = sum max_sub_ary = sub_ary.dup end break if done end return max_sub_ary, max_sum end end

on 2007-07-16 06:27

This was a nice diversion on Friday morning at the start of my kids' championship swim meet. I had to work Saturday and Sunday so the last two test cases had to wait until now (yes, I should be sleeping!). -Rob Rob Biedenharn http://agileconsultingllc.com Rob@AgileConsultingLLC.com class Array # Given an Array of numbers, return the contiguous sub-array having the # maximum sum of its elements. Longer sub-arrays are preferred. # #-- # (or members of any Ring having operations '+' (binary, associative and # commutative) and '-' (unary, giving the inverse with respect to '+')) #++ def sub_max identity=0 return self if size < 2 # nothing to sum! ms = Array.new(size) { Array.new(size) {identity} } mx, range = self[0], 0..0 0.upto(size-1) do |e| e.downto(0) do |s| current = ms[s][e] = if s == e self[s] else ms[s][e-1] + ms[s+1][e] + (- ms[s+1] [e-1]) end if current > mx || current == mx && (e - s + 1) > (range.end - range.begin + 1) mx = current range = s..e end end end self[range] end end if __FILE__ == $0 require 'test/unit' class Array def put2d print '[ ' each do |row| row.put1d print ",\n " end puts ']' end def put1d print '[ ' each do |item| print("%3d, " % item) end print ']' end end class SubMaxTest < Test::Unit::TestCase def test_quiz_example input = [-1, 2, 5, -1, 3, -2, 1] expected = [2, 5, -1, 3] assert_equal expected, input.sub_max end def test_empty assert_equal [], [].sub_max end def test_single assert_equal [ 0], [ 0].sub_max assert_equal [-1], [-1].sub_max assert_equal [ 1], [ 1].sub_max end def test_all_positive input = [ 1, 2, 4, 8 ] assert_equal input, input.sub_max end def test_all_non_negative input = [ 1, 2, 0, 4 ] assert_equal input, input.sub_max end def test_all_negative input = [ -1, -2, -3, -9 ] assert_equal [-1], input.sub_max input = [ -2, -1, -3, -9 ] assert_equal [-1], input.sub_max, 'need to test diagonal' end def test_prefer_length_earlier input = [ -1, 0, 1, -2, -9 ] assert_equal [0, 1], input.sub_max, "if actual is [1], need to add a length test on range" end def test_prefer_length_later input = [ -1, 1, 0, -2, -9 ] assert_equal [1, 0], input.sub_max, "if actual is [1], need to add a length test on range" end def test_prefer_length_multiple_options input = [ 1, 2, 3, -6, 6 ] # options # [6] # [1,2,3] expected = [ 1, 2, 3, -6, 6 ] assert_equal expected, input.sub_max, "if [6] or [1,2,3] you can do better" end end end __END__

on 2007-07-16 17:30

Here's my solution to the maximum sub-array problem. I'm sure my algorithm is not optimal, but it's readable and concise: # file: max_sub_array.rb # author: Drew Olson class Array alias :orig_to_s :to_s # sum the integer values of array contents def int_sum self.inject(0){|sum,i| sum+i.to_i} end # find the maximum sub array in an array def max_sub_array (0...self.size).inject([self.first]) do |max_sub,i| (i...self.size).each do |j| if max_sub.int_sum < self[i..j].int_sum max_sub = self[i..j] end end max_sub end end # pretty printing for array def to_s self.inject("[") do |str,i| str + "#{i}, " end[0...-2] + "]" end end # test example if __FILE__ == $0 my_arr = [-1, 2, 5, -1, 3, -2, 1] puts "array: #{my_arr}" puts "maximum sub-array: #{my_arr.max_sub_array}" end

on 2007-07-17 01:03

Solution #1: Array is bound to arr sub_arrs = [] arr.each_index{|i| (i...arr.length).each{|i2| sub_arrs << arr[i..i2]}} p sub_arrs.sort_by{|arr| arr.inject(0){|s,n|s+n}}.last Solution #2: Array is bound to a p (b=(0...(l=a.size)).to_a).zip([b]*l).map{|(i,s)|s.map{|j|a[i,j]}}.sort_by{|a|a.map!{|a|[a.inject(0){|s,n|s+n},a]}.sort![-1][0]}[-1][-1][-1]

on 2007-07-17 16:04

A late late entry (I was busy yesterday). Yes it does an exhaustive search, but for even moderate sized sets, it's feasibly fast enough. class Array def sum() s=0 each{|i| s+=i} s end end array=[-6,-5,-4,-3,-2,-1,0,1,2,3,-5,4,5,6] maxIndex = array.length-1 sizeByRange = {} 0.upto(maxIndex) do |start| start.upto(maxIndex) do |endI| sizeByRange.store(array[start..endI].sum,start..endI) #puts "subarray #{start} to #{endI} sums to #{array[start..endI].sum}" end end puts "Minimum array is [#{array[sizeByRange.min[1]].join(',')}]" puts "Maximum array is [#{array[sizeByRange.max[1]].join(',')}]"

on 2007-07-17 18:49

Just a note on my "solution" I sent in earlier... Well, it's not entirely correct... I've been shown at least one case that fails. It's probably not that far off, but unfortunately I don't have time this week to correct it... Just so no summaries go using it.

on 2007-07-17 19:03

On Jul 17, 2007, at 11:12 AM, Matthew Moss wrote: > Just a note on my "solution" I sent in earlier... Well, it's not > entirely correct... I've been shown at least one case that fails. > It's probably not that far off, but unfortunately I don't have time > this week to correct it... Just so no summaries go using it. Next week's quiz: debug Matthew's solution. ;) James Edward Gray II

on 2007-07-18 05:22

On 7/13/07, Ruby Quiz <james@grayproductions.net> wrote: > Extra Credit: > > Given a matrix of integers, find the rectangle with maximum sum. > > # # This is roughly the same matrix solution I posted before. # Sorry for the double post. Two lines in the middle of the program were # too long and got wrapped in the post. # I made the lines shorter and tried again. # # Here is my matrix solution. # It does the Matrix extra credit. # If there are multiple rectangles that equal max sum, it prints all of them. # # Since the quiz did not specify how to input, # I just hard coded a sample Matrix at the beginning. require 'matrix' mat=Matrix[[7,-1,2,3,-4],[-7,8,-22,10,11],[3,15,16,17,-18],[4,22,-23,-24,-25]] s = [] (0...mat.row_size).each do |a| (0...mat.column_size).each do |b| (1..mat.row_size).each do |x| (1..mat.column_size).each do |y| s << mat.minor(a,x,b,y) end end end end tot = s.uniq.map {|x| x.to_a} bg=tot.max{|x,y|x.flatten.inject(0){|a,b|a+b}<=>y.flatten.inject(0){|c,d|c+d}} sb=tot.select{|r|r.flatten.inject(0){|a,b|a+b}==bg.flatten.inject(0){|c,d|c+d}} puts "Original Matrix" (0...mat.row_size).each do |x| print mat.row(x).to_a.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n" end puts puts "Solutions" sb.each do |x| puts x.each {|y| print y.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"} end # Harry

on 2007-07-18 11:06

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

on 2007-07-18 16:19

Eh.... I got some better quizzes in mind than debugging my lousy code... I just have to write them up. (This thing called "day job" keeps getting in the way...)

on 2007-07-18 16:30

On Jul 18, 2007, at 9:17 AM, Matthew Moss wrote: > Eh.... I got some better quizzes in mind than debugging my lousy > code... I just have to write them up. (This thing called "day job" > keeps getting in the way...) I always enjoy your quizzes Matthew. Looking forward to it. James Edward Gray II

on 2007-07-19 02:13

Oh, these quizzes. I need to either find more time to play with them or stop telling myself I don't have the time. I did this in Perl for a job interview a while ago and happened to still have it handy, so all I did was translate it (somewhat) into Ruby. ------------------------------------------------------------------------------- class Array def largest_sum_sequence # initialize with a sequence of the first number largest = { :sum => first, :start => 0, :end => 0 } (0 .. length-1).each do |start_i| sum = 0 start_num = self[start_i] # don't bother with a sequence that starts with a negative number # but what if all the numbers are negative? next if largest[:sum] > start_num and start_num < 0 (start_i .. length-1).each do |end_i| end_num = self[end_i] sum += end_num # if this sequence is the largest so far if sum > largest[:sum] largest[:sum] = sum largest[:start] = start_i largest[:end] = end_i end end end puts "Largest sum: #{largest[:sum]}" puts "The sequence starts at element #{largest[:start]} and goes to element #{largest[:end]}" puts "The sequence is #{self[largest[:start] .. largest[:end]].join(' ')}" end end numbers = ARGV.collect { |arg| arg.to_i } numbers.largest_sum_sequence

on 2007-09-25 23:01

On Jul 13, 2007, at 11:10 AM, Kyle Schmitt wrote: > Am I missing something, or is this one of the easiest quizzes that's > been put forward? It's a pretty easy problem. I almost rejected it for that reason. I was just sure I could do it with a one-liner, but when my own solution didn't make it down to that I accepted the problem. I'm sure someone will get it down there, but I didn't so it required a touch more thought than I expected. We've had some pretty easy problems. FizzBuzz was pretty close to this level. I'm fine with that thought. Ruby Quiz is for all levels. James Edward Gray II

on 2007-09-25 23:02

> Am I missing something, or is this one of the easiest quizzes that's > been put forward? Well, you're missing the fizzfuzz quiz.

on 2007-09-25 23:03

On Fri, 13 Jul 2007 19:47:11 +0200, anansi wrote: > > but why is [2, 5, -1, 3] sum= 9 the sub-array with the maximum sum? > wouldn't be [2,5,3,1] sum=11 the right solution? Because the subarrays in the quiz problem must be contiguous. The answer to your proposed version is ARRAY=[-1, 2, 5, -1, 3, -2, 1] ARRAY.select{|x| x>=0} --Ken

on 2007-09-25 23:03

Kyle Schmitt wrote, On 7/13/2007 11:10 AM: > Am I missing something, or is this one of the easiest quizzes that's > been put forward? > > --Kyle > > > Well, you could put a maximum time complexity constraint on it and the solutions aren't as obvious (unless you've seen it before)

on 2007-09-25 23:04

could someone explain this please? I really don't understand this quiz? 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] I know what an array is :) I know what integers are :) I know what a sum is :) but why is [2, 5, -1, 3] sum= 9 the sub-array with the maximum sum? wouldn't be [2,5,3,1] sum=11 the right solution? -- greets one must still have chaos in oneself to be able to give birth to a dancing star

on 2007-09-25 23:04

On Jul 13, 2007, at 2:29 PM, Ari Brown wrote: > Being a nub at life, liberty, and ruby, what is the best way to > search it? Would it be to go and sum up the elements in every > possible array (ie, [abc] => [a]. [b]. [c]. [ab]. [bc])? Because > that seems like it would get very CPU consuming with larger arrays. An exhaustive search would have execution time on the order of N**2, where N is the length of the array. That's not great but its not horrible either -- that is, not nearly so bad as a search that takes exponential (e**N) time. Regards, Morton

on 2007-09-25 23:05

On 7/13/07, anansi <kazaam@oleco.net> wrote: > is :) > > but why is [2, 5, -1, 3] sum= 9 the sub-array with the maximum sum? > wouldn't be [2,5,3,1] sum=11 the right solution? A sub-array is a contiguous list within the overall array. For [a,b,c], the sub-arrays are [a], [b], [c], [a,b], [b,c] and of course [a,b,c], but [a,c] is NOT a sub-array because the elements are not contiguous within the overall array. I'm looking forward to tackling this quiz this evening, what a rocking Friday night it will be! :) Matt

on 2007-09-25 23:05

Humm. OK well fizbuzz could be done as a one liner..... a reasonably readable version of this one looks like 10 lines to me..... yea just tried to shorten it. My version of this one can only condense down to 2 lines, and I don't wanna spend the time to do more on it, considering the whole, at work thing :) --Kyle

on 2007-09-25 23:06

On Jul 13, 2007, at 10:56 AM, David Chelimsky wrote: > > Does it matter? I think either selection would be acceptable. I would probably favor the shorter one, but I don't think it matters. James Edward Gray II

on 2007-09-25 23:07

```
On 7/13/07, Sammy Larbi <sam@powersource.com> wrote:
> solutions aren't as obvious (unless you've seen it before)
Thank you I felt completely stupid in desperately searching for a
O(n*log n) solution...
Robert
```

on 2007-09-25 23:07

On Jul 13, 2007, at 1:29 PM, Ari Brown wrote: > Being a nub at life, liberty, and ruby, what is the best way to > search it? Would it be to go and sum up the elements in every > possible array (ie, [abc] => [a]. [b]. [c]. [ab]. [bc])? Because > that seems like it would get very CPU consuming with larger arrays. Let's have this discussion after the no-spoiler period, please. James Edward Gray II

on 2007-09-25 23:08

<snip> Being a nub at life, liberty, and ruby, what is the best way to search it? Would it be to go and sum up the elements in every possible array (ie, [abc] => [a]. [b]. [c]. [ab]. [bc])? Because that seems like it would get very CPU consuming with larger arrays. aRi --------------------------------------------| If you're not living on the edge, then you're just wasting space.

on 2007-09-25 23:08

Am I missing something, or is this one of the easiest quizzes that's been put forward? --Kyle

on 2007-09-25 23:09

On 7/13/07, Kyle Schmitt <kyleaschmitt@gmail.com> wrote: > yea just tried to shorten it. My version of this one can only > condense down to 2 lines, and I don't wanna spend the time to do more > on it, considering the whole, at work thing :) I've golfed mine down to a 108-char method body for an exhaustive search...

on 2007-09-25 23:10

On 7/13/07, David Chelimsky <dchelimsky@gmail.com> wrote: > What are the criteria for selecting from multiple possibilities? For example: > > [1,2,3,-7,6] Or this: [1,2,3,-6,6] options [1,2,3] [1,2,3,-6,6] [6]