# \[QUIZ\] Maximum Sub-Array (#131)

**URL:** <https://rubytalk.org/t/quiz-maximum-sub-array-131/39080>\
**Category:** ruby-talk\
**Created:** [13 July 2007 14:29 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080 "2007-07-13T14:29:03Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [13 July 2007 14:29 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/1 "2007-07-13T14:29:03Z")

</div>

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/](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:
> 
> &nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1]  
> &nbsp;&nbsp;maximum sub-array: [2, 5, -1, 3]
> 
> Extra Credit:
> 
> Given a matrix of integers, find the rectangle with maximum sum.

---

<div class="post-metadata">

**Author:** ![Matt\_Greer](https://avatars.discourse-cdn.com/v4/letter/m/47e85d/32.png) [@Matt\_Greer](https://rubytalk.org/u/Matt_Greer)\
**Post date:** [13 July 2007 14:48 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/2 "2007-07-13T14:48:04Z")

</div>

> by Harlan
> 
> Given an array of integers, find the sub-array with maximum sum. For  
> example:
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maximum sub-array: [2, 5, -1, 3]

Just to confirm the problem. Wouldn't the maximum sub array be

[2, 5, 3] ?

Matt

---

<div class="post-metadata">

**Author:** ![Paul\_Novak](https://avatars.discourse-cdn.com/v4/letter/p/5f9b8f/32.png) [@Paul\_Novak](https://rubytalk.org/u/Paul_Novak)\
**Post date:** [13 July 2007 15:42 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/3 "2007-07-13T15:42:08Z")

</div>

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:   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;or [-1] ?

Regards,

Paul.

> **···**
>
> On Jul 13, 10: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/](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:
> > 
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1]  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maximum sub-array: [2, 5, -1, 3]
> > 
> > Extra Credit:
> > 
> > Given a matrix of integers, find the rectangle with maximum sum.

---

<div class="post-metadata">

**Author:** ![Harry3](https://avatars.discourse-cdn.com/v4/letter/h/54ee81/32.png) [@Harry3](https://rubytalk.org/u/Harry3)\
**Post date:** [15 July 2007 14:39 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/4 "2007-07-15T14:39:21Z")

</div>

> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> by Harlan
> 
> Given an array of integers, find the sub-array with maximum sum. For example:
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maximum sub-array: [2, 5, -1, 3]
> 
> Extra Credit:
> 
> 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
> 
> --  
> A Look into Japanese Ruby List in English
> 
> > **[Kakueki.com is for sale | HugeDomains](https://www.hugedomains.com/domain_profile.cfm?d=kakueki.com)**
> >
> > Start using this domain right away. Straightforward domain shopping experience. Quick access to your domain.

---

<div class="post-metadata">

**Author:** ![Ken\_Bloom](https://avatars.discourse-cdn.com/v4/letter/k/f08c70/32.png) [@Ken\_Bloom](https://rubytalk.org/u/Ken_Bloom)\
**Post date:** [15 July 2007 14:40 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/5 "2007-07-15T14:40:15Z")

</div>

> 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/](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.
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

> **···**
>
> On Fri, 13 Jul 2007 23:29:03 +0900, Ruby Quiz wrote:  
> =-=-=-=-=
> 
> > by Harlan
> > 
> > Given an array of integers, find the sub-array with maximum sum. For  
> > example:
> > 
> > &nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1] maximum sub-array:
> 
> [2, 5,
> 
> > &nbsp;&nbsp;-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  
> &nbsp;&nbsp;&nbsp;def argmax  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curmax=nil  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curval=nil  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;each do |x|  
> &nbsp;&nbsp;&nbsp;t=yield x  
> &nbsp;&nbsp;&nbsp;if not curmax or (curmax \< t)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curmax=t  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curval=x  
> &nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curval  
> &nbsp;&nbsp;&nbsp;end
> 
> &nbsp;&nbsp;&nbsp;def sum  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inject{|a,b|a+b}  
> &nbsp;&nbsp;&nbsp;end
> 
> &nbsp;&nbsp;&nbsp;def subarrays  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result=  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(0...length).each do |start|  
> &nbsp;&nbsp;&nbsp;((start + 1)..length).each do |finish|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result \<\< self[start...finish]  
> &nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result  
> &nbsp;&nbsp;&nbsp;end  
> end
> 
> class Matrix  
> &nbsp;&nbsp;&nbsp;include Enumerable  
> &nbsp;&nbsp;&nbsp;def submatrices  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result=  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(0...row\_size).each do |srow|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(srow+1..row\_size).each do |erow|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(0...column\_size).each do |scolumn|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(scolumn+1..column\_size).each do |ecolumn|  
> &nbsp;&nbsp;&nbsp;result \<\< minor(srow...erow,scolumn...ecolumn)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end end end end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result  
> &nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;def each  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(0...row\_size).each do |row|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(0...column\_size).each do |column|  
> &nbsp;&nbsp;&nbsp;yield self[row,column]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end end  
> &nbsp;&nbsp;&nbsp;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/](http://www.iit.edu/~kbloom1/)

---

<div class="post-metadata">

**Author:** ![Henrik\_Schmidt-Molle](https://avatars.discourse-cdn.com/v4/letter/h/df705f/32.png) [@Henrik\_Schmidt-Molle](https://rubytalk.org/u/Henrik_Schmidt-Molle)\
**Post date:** [15 July 2007 14:47 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/6 "2007-07-15T14:47:20Z")

</div>

Ruby Quiz wrote:

> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> by Harlan
> 
> Given an array of integers, find the sub-array with maximum sum. For example:
> 
> &nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1]  
> &nbsp;&nbsp;maximum sub-array: [2, 5, -1, 3]
> 
> Extra Credit:  
> 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)

&nbsp;&nbsp;if (max = arr.max) \<= 0  
&nbsp;&nbsp;&nbsp;&nbsp;# if all the numbers in the array are less than or equal to zero,  
&nbsp;&nbsp;&nbsp;&nbsp;# then the maximum subarray is simply the array  
&nbsp;&nbsp;&nbsp;&nbsp;# consisting of the largest value  
&nbsp;&nbsp;&nbsp;&nbsp;max\_idx = arr.index(max)  
&nbsp;&nbsp;&nbsp;&nbsp;return max, max\_idx, max\_idx  
&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;# starting index of the maximum subarray  
&nbsp;&nbsp;x1 = 0

&nbsp;&nbsp;# ending index of the maximum subarray  
&nbsp;&nbsp;x2 = 0  
&nbsp;&nbsp;&nbsp;# the maximum value found so far  
&nbsp;&nbsp;running\_max = 0  
&nbsp;&nbsp;&nbsp;# the maximum value of the array ending on the current  
&nbsp;&nbsp;# value (in the block below) or zero, if the maximum  
&nbsp;&nbsp;# array becomes negative by including the current value  
&nbsp;&nbsp;max\_ending\_here = 0

&nbsp;&nbsp;# the start index of a possible maximum subarray  
&nbsp;&nbsp;start\_idx = 0  
&nbsp;&nbsp;&nbsp;arr.each\_with\_index do |i, idx|  
&nbsp;&nbsp;&nbsp;&nbsp;start\_idx = idx if max\_ending\_here == 0  
&nbsp;&nbsp;&nbsp;&nbsp;max\_ending\_here = [0, max\_ending\_here + i].max  
&nbsp;&nbsp;&nbsp;&nbsp;if max\_ending\_here \> running\_max  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;running\_max = max\_ending\_here  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x1 = start\_idx  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x2 = idx  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;return running\_max, x1, x2  
end

# Running time: O(m^2 \* n)  
def max\_submatrix(matrix)

&nbsp;&nbsp;# We already have a nice linear algorithm for solving  
&nbsp;&nbsp;# the problem in one dimension. What we want to do is  
&nbsp;&nbsp;# basically to reduce the problem to an array, and then  
&nbsp;&nbsp;# solve that problem using max\_subarray.  
&nbsp;&nbsp;# The problem can be solved this way for any contiguous  
&nbsp;&nbsp;# number of rows by simply adding them together, thereby  
&nbsp;&nbsp;# "collapsing" them into one row, and then going from there.  
&nbsp;&nbsp;# Now, we want to do this efficiently, so we create  
&nbsp;&nbsp;# a cumulative matrix, by adding the elements of the columns  
&nbsp;&nbsp;# together. That way, we only need to look up one value  
&nbsp;&nbsp;# pr. column to get the sums of the columns in any sub matrix.  
&nbsp;&nbsp;c\_matrix = matrix.inject() do |memo, arr|  
&nbsp;&nbsp;&nbsp;&nbsp;prev\_arr = memo.last  
&nbsp;&nbsp;&nbsp;&nbsp;memo \<\< (prev\_arr == nil ? arr : Array.new(arr.size) { |i| prev\_arr[i] + arr[i] })  
&nbsp;&nbsp;end

&nbsp;&nbsp;# the maximum value found so far  
&nbsp;&nbsp;running\_max = 0  
&nbsp;&nbsp;&nbsp;# starting index of the horizontal maximum subarray  
&nbsp;&nbsp;x1 = 0  
&nbsp;&nbsp;&nbsp;# ending index of the horizontal maximum subarray  
&nbsp;&nbsp;x2 = 0

&nbsp;&nbsp;# starting index of the vertical maximum subarray  
&nbsp;&nbsp;y1 = 0

&nbsp;&nbsp;# ending index of the vertical maximum subarray  
&nbsp;&nbsp;y2 = 0  
&nbsp;&nbsp;&nbsp;c\_matrix.each\_with\_index do |c\_arr, vert\_iter\_end|  
&nbsp;&nbsp;&nbsp;&nbsp;0.upto(vert\_iter\_end) do |vert\_iter\_start|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr = c\_arr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if vert\_iter\_start != vert\_iter\_end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr = Array.new(c\_arr.size) { |i| c\_arr[i] - c\_matrix[vert\_iter\_start][i] }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c\_max, hz\_s, hz\_e = max\_subarray(arr)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if c\_max \> running\_max  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;running\_max = c\_max  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x1, x2, y2 = hz\_s, hz\_e, vert\_iter\_end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y1 = vert\_iter\_start == vert\_iter\_end ? 0 : vert\_iter\_start + 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;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 =  
[  
&nbsp;&nbsp;[1, 5, -3, 4],  
&nbsp;&nbsp;[-8, 2, 9, 12],  
&nbsp;&nbsp;[6, 1, -2, 2],  
&nbsp;&nbsp;[-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}"

> **···**
>
> \*

---

<div class="post-metadata">

**Author:** ![Eric\_I2](https://avatars.discourse-cdn.com/v4/letter/e/22d042/32.png) [@Eric\_I2](https://rubytalk.org/u/Eric_I2)\
**Post date:** [15 July 2007 14:50 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/7 "2007-07-15T14:50:00Z")

</div>

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)  
&nbsp;&nbsp;(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)  
&nbsp;&nbsp;(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](http://LearnRuby.com)

---

<div class="post-metadata">

**Author:** ![Alexandru\_E\_Ungur](https://avatars.discourse-cdn.com/v4/letter/a/c0e974/32.png) [@Alexandru\_E\_Ungur](https://rubytalk.org/u/Alexandru_E_Ungur)\
**Post date:** [15 July 2007 15:24 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/8 "2007-07-15T15:24:05Z")

</div>

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

[quiz131.rb](https://rubytalk.org/uploads/short-url/7URSYP5B4oq1kFPxm3Vp2O4LzPI.rb) (565 Bytes)

---

<div class="post-metadata">

**Author:** ![Harry3](https://avatars.discourse-cdn.com/v4/letter/h/54ee81/32.png) [@Harry3](https://rubytalk.org/u/Harry3)\
**Post date:** [15 July 2007 15:24 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/9 "2007-07-15T15:24:56Z")

</div>

> Extra Credit:
> 
> Given a matrix of integers, find the rectangle with maximum sum.

> **···**
>
> On 7/13/07, Ruby Quiz \<james@grayproductions.net\> wrote:  
> #  
> # 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|  
> &nbsp;&nbsp;(0...mat.column\_size).each do |b|  
> &nbsp;&nbsp;&nbsp;&nbsp;(1..mat.row\_size).each do |x|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(1..mat.column\_size).each do |y|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s \<\< mat.minor(a,x,b,y)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;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  
> &nbsp;&nbsp;x.each {|y| print y.map{|m| m.to\_s.rjust(tot.flatten.max.to\_s.length+2)},"\n"}  
> end
> 
> # Harry
> 
> --  
> A Look into Japanese Ruby List in English
> 
> > **[Kakueki.com is for sale | HugeDomains](https://www.hugedomains.com/domain_profile.cfm?d=kakueki.com)**
> >
> > Start using this domain right away. Straightforward domain shopping experience. Quick access to your domain.

---

<div class="post-metadata">

**Author:** ![Morton\_Goldberg](https://avatars.discourse-cdn.com/v4/letter/m/7ea924/32.png) [@Morton\_Goldberg](https://rubytalk.org/u/Morton_Goldberg)\
**Post date:** [15 July 2007 15:44 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/10 "2007-07-15T15:44:32Z")

</div>

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)  
&nbsp;&nbsp;&nbsp;&nbsp;max\_sum = arry.inject { |sum, n| sum += n }  
&nbsp;&nbsp;&nbsp;&nbsp;min\_length = arry.size  
&nbsp;&nbsp;&nbsp;&nbsp;result = arry  
&nbsp;&nbsp;&nbsp;&nbsp;(1...arry.size).each do |i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(i...arry.size).each do |j|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sub = arry[i..j]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum = sub.inject { |sum, n| sum += n }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next if sum \< max\_sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next if sum == max\_sum && sub.size \>= min\_length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max\_sum, min\_length, result = sum, sub.size, sub  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;result  
end  
\</code\>

Regards, Morton

---

<div class="post-metadata">

**Author:** ![Jesse\_Merriman](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@Jesse\_Merriman](https://rubytalk.org/u/Jesse_Merriman)\
**Post date:** [15 July 2007 15:46 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/11 "2007-07-15T15:46:55Z")

</div>

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.

[max\_subarray.rb](https://rubytalk.org/uploads/short-url/nLuM9IuVZ9a0fJVXt4LPCwe1tvS.rb) (3.93 KB)

> **···**
>
> --  
> Jesse Merriman  
> [jessemerriman@warpmail.net](mailto:jessemerriman@warpmail.net)  
> [http://www.jessemerriman.com/](http://www.jessemerriman.com/)

---

<div class="post-metadata">

**Author:** ![Carl\_Porth](https://avatars.discourse-cdn.com/v4/letter/c/73ab20/32.png) [@Carl\_Porth](https://rubytalk.org/u/Carl_Porth)\
**Post date:** [15 July 2007 15:55 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/12 "2007-07-15T15:55:05Z")

</div>

#!/usr/bin/env ruby

require "rubygems"  
require "facets"  
require "enumerable/each\_unique\_pair"  
require "enumerable/sum"

class Array  
&nbsp;&nbsp;# all contiguous subarrays  
&nbsp;&nbsp;def sub\_arrays  
&nbsp;&nbsp;&nbsp;&nbsp;[\*0..self.size].to\_enum(:each\_unique\_pair).map { |a,b|  
self[a..b-1] }  
&nbsp;&nbsp;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/](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:
> > 
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1]  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maximum sub-array: [2, 5, -1, 3]
> > 
> > Extra Credit:
> > 
> > Given a matrix of integers, find the rectangle with maximum sum.

---

<div class="post-metadata">

**Author:** ![Todd\_Benson](https://avatars.discourse-cdn.com/v4/letter/t/34f0e0/32.png) [@Todd\_Benson](https://rubytalk.org/u/Todd_Benson)\
**Post date:** [15 July 2007 15:56 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/13 "2007-07-15T15:56:44Z")

</div>

Just like many others, I went for brute force with some readability.  
Golf solution at the bottom.

class Array  
&nbsp;&nbsp;def sum  
&nbsp;&nbsp;&nbsp;&nbsp;inject {|sum, elem| sum + elem}  
&nbsp;&nbsp;end  
&nbsp;&nbsp;def sub\_arrays  
&nbsp;&nbsp;&nbsp;&nbsp;subs = []  
&nbsp;&nbsp;&nbsp;&nbsp;0.upto(size-1) { |i| i.upto(size-1) { |j| subs \<\< self[i..j] } }  
&nbsp;&nbsp;&nbsp;&nbsp;subs  
&nbsp;&nbsp;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

---

<div class="post-metadata">

**Author:** ![Justin\_Ethier](https://avatars.discourse-cdn.com/v4/letter/j/c67d28/32.png) [@Justin\_Ethier](https://rubytalk.org/u/Justin_Ethier)\
**Post date:** [15 July 2007 21:04 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/14 "2007-07-15T21:04:39Z")

</div>

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  
&nbsp;&nbsp;def initialize  
&nbsp;&nbsp;&nbsp;&nbsp;@start = 0  
&nbsp;&nbsp;&nbsp;&nbsp;@end = 0  
&nbsp;&nbsp;&nbsp;&nbsp;@sum = 0  
&nbsp;&nbsp;end

&nbsp;&nbsp;# Set boundaries of the sub-array  
&nbsp;&nbsp;def set\_bounds(list\_start, list\_end)  
&nbsp;&nbsp;&nbsp;&nbsp;@start, @end = list\_start, list\_end  
&nbsp;&nbsp;end

&nbsp;&nbsp;# Provide get/set accessors  
&nbsp;&nbsp;attr\_reader :start, :end, :sum  
&nbsp;&nbsp;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  
&nbsp;&nbsp;# Finds the sub-array with the largest sum  
&nbsp;&nbsp;# Input: a list of integers  
&nbsp;&nbsp;def find(list)  
&nbsp;&nbsp;&nbsp;&nbsp;max = SubArray.new  
&nbsp;&nbsp;&nbsp;&nbsp;cur = SubArray.new

&nbsp;&nbsp;&nbsp;&nbsp;for i in 0...list.size  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cur.sum = cur.sum + list[i]

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (cur.sum \> max.sum)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max.sum = cur.sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cur.set\_bounds(cur.start, i)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max.set\_bounds(cur.start, i)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elsif (cur.sum \< 0)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# If sum goes negative, this region cannot have the max sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cur.sum = 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cur.set\_bounds(i + 1, i + 1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;list.slice(max.start, max.end - max.start + 1)  
&nbsp;&nbsp;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  
&nbsp;&nbsp;def setup  
&nbsp;&nbsp;&nbsp;&nbsp;@ma = MaxSubArray.new  
&nbsp;&nbsp;end

&nbsp;&nbsp;def test\_max\_sub\_array  
&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([2, 5, -1, 3], @ma.find([-1, 2, 5, -1, 3, -2, 1]))  
&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([10], @ma.find([-1, 2, 5, -1, 3, -2, -12, 10]))  
&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal(@ma.find([-25, 81, -14, 43, -23, 86, -65, 48]), [81, -14,  
43, -23, 86])  
&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([9, 11, 23, -5, 15, 18, 6, -18, 21, -4,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-17, -19, -10, -9, 19, 17, 24, 10, 21, -23, -25,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18, -22,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6, 10,  
4,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23],  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@ma.find([-16, -8, 9, 11, 23, -5, 15, 18, 6, -18, 21, -4,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-17, -19, -10, -9, 19, 17, 24, 10, 21, -23, -25,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18, -22,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6, 10,  
4,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23, -23,  
16,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-19, -10, 12, -17, -9, 6, -8, -23, 16, -17, -10,  
24,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-1, -6, -24, -5, 16, -11, -7, -8, 12, -21, -23,  
-8,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-8, 4, 7, 6, -22, -8, -19, -7, 23, 4, 9, -19,  
-19, 0, -15]))  
&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26, 9, 30, 31,  
16, 44, 20, 10, 55, 28,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17, 38,  
-5, -28, 45, -38, 4,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32,  
-22, 8, 37, 57, 13, 17,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24, 34,  
-10, -26, -27, 12, 5, -2,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56, 10,  
-35, -29, 40, -1, 30, 45, 36],  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@ma.find([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26, 9,  
30, 31, 16, 44, 20, 10, 55, 28,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17, 38,  
-5, -28, 45, -38, 4,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32,  
-22, 8, 37, 57, 13, 17,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24, 34,  
-10, -26, -27, 12, 5, -2,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56, 10,  
-35, -29, 40, -1, 30, 45, 36, -38, 30, -28]))  
&nbsp;&nbsp;end  
end

Thanks,

Justin

> **···**
>
> On 7/13/07, Ruby Quiz \<james@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/](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:
> > 
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;array: [-1, 2, 5, -1, 3, -2, 1]  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;maximum sub-array: [2, 5, -1, 3]
> > 
> > Extra Credit:
> > 
> > Given a matrix of integers, find the rectangle with maximum sum.

---

<div class="post-metadata">

**Author:** ![Michael\_Glaesemann](https://avatars.discourse-cdn.com/v4/letter/m/bc79bd/32.png) [@Michael\_Glaesemann](https://rubytalk.org/u/Michael_Glaesemann)\
**Post date:** [15 July 2007 21:17 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/15 "2007-07-15T21:17:56Z")

</div>

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  
&nbsp;&nbsp;&nbsp;def max\_sub\_array  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.max\_sub\_arrayr[0]  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def max\_sub\_arrayr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ary = self.clone  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sub\_ary = Array.new.push(ary.shift)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum = sub\_ary[0]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max\_sub\_ary = sub\_ary.dup  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max\_sum = sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;done = false  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ary.each\_with\_index do |n,i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if sum \> 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if sum + n \> 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum += n  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sub\_ary.push(n)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sub\_ary, sum = ary.slice(i+1..(ary.size-1)).max\_sub\_arrayr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;done = true  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elsif sum \<= n  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sub\_ary, sum = ary.slice(i..(ary.size-1)).max\_sub\_arrayr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;done = true  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if sum \> max\_sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max\_sum = sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max\_sub\_ary = sub\_ary.dup  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break if done  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return max\_sub\_ary, max\_sum  
&nbsp;&nbsp;&nbsp;end  
end

Michael Glaesemann  
grzm seespotcode net

---

<div class="post-metadata">

**Author:** ![Matthew\_D\_Moss](https://avatars.discourse-cdn.com/v4/letter/m/b9e5f3/32.png) [@Matthew\_D\_Moss](https://rubytalk.org/u/Matthew_D_Moss)\
**Post date:** [15 July 2007 23:55 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/16 "2007-07-15T23:55:05Z")

</div>

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)  
&nbsp;&nbsp;&nbsp;a = b = x = 0  
&nbsp;&nbsp;&nbsp;arr.each\_with\_index do |e, i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b = [b + e, 0].max  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;unless a \> b  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a, x = b, i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;return x  
end

def max\_subarray(arr)  
&nbsp;&nbsp;&nbsp;i = arr.size - max\_subarray\_last\_index(arr.reverse) - 1  
&nbsp;&nbsp;&nbsp;j = max\_subarray\_last\_index(arr)  
&nbsp;&nbsp;&nbsp;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] )

---

<div class="post-metadata">

**Author:** ![Rob\_Biedenharn1](https://avatars.discourse-cdn.com/v4/letter/r/57b2e6/32.png) [@Rob\_Biedenharn1](https://rubytalk.org/u/Rob_Biedenharn1)\
**Post date:** [16 July 2007 04:26 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/17 "2007-07-16T04:26:46Z")

</div>

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](http://agileconsultingllc.com)  
[Rob@AgileConsultingLLC.com](mailto:Rob@AgileConsultingLLC.com)

class Array  
&nbsp;&nbsp;&nbsp;# Given an Array of numbers, return the contiguous sub-array having the  
&nbsp;&nbsp;&nbsp;# maximum sum of its elements. Longer sub-arrays are preferred.

> **···**
>
> #  
> &nbsp;&nbsp;&nbsp;#--  
> &nbsp;&nbsp;&nbsp;# (or members of any Ring having operations '+' (binary, associative and  
> &nbsp;&nbsp;&nbsp;# commutative) and '-' (unary, giving the inverse with respect to '+'))  
> &nbsp;&nbsp;&nbsp;#++  
> &nbsp;&nbsp;&nbsp;def sub\_max identity=0  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return self if size \< 2 # nothing to sum!
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ms = Array.new(size) { Array.new(size) {identity} }  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mx, range = self[0], 0..0  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0.upto(size-1) do |e|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e.downto(0) do |s|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;current = ms[s][e] = if s == e  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self[s]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ms[s][e-1] + ms[s+1][e] + (- ms[s+1][e-1])  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if current \> mx || current == mx && (e - s + 1) \> (range.end - range.begin + 1)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mx = current  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;range = s..e  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self[range]  
> &nbsp;&nbsp;&nbsp;end  
> end
> 
> if \_\_FILE\_\_ == $0  
> &nbsp;&nbsp;&nbsp;require 'test/unit'
> 
> &nbsp;&nbsp;&nbsp;class Array  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def put2d  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print '[ '  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;each do |row|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;row.put1d  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print ",\n "  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts ']'  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def put1d  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print '[ '  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;each do |item|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print("%3d, " % item)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print ']'  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;end
> 
> &nbsp;&nbsp;&nbsp;class SubMaxTest \< Test::Unit::TestCase  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_quiz\_example  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [-1, 2, 5, -1, 3, -2, 1]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expected = [2, 5, -1, 3]
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal expected, input.sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_empty  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [], [].sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_single  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [0], [0].sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [-1], [-1].sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [1], [1].sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_all\_positive  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [1, 2, 4, 8]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal input, input.sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_all\_non\_negative  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [1, 2, 0, 4]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal input, input.sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_all\_negative  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [-1, -2, -3, -9]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [-1], input.sub\_max  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [-2, -1, -3, -9]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [-1], input.sub\_max, 'need to test diagonal'  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_prefer\_length\_earlier  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [-1, 0, 1, -2, -9]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [0, 1], input.sub\_max, "if actual is [1], need to add a length test on range"  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_prefer\_length\_later  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [-1, 1, 0, -2, -9]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal [1, 0], input.sub\_max, "if actual is [1], need to add a length test on range"  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def test\_prefer\_length\_multiple\_options  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input = [1, 2, 3, -6, 6]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# options  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# [6]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# [1,2,3]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expected = [1, 2, 3, -6, 6]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal expected, input.sub\_max, "if [6] or [1,2,3] you can do better"  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;end  
> end  
> \_\_END\_\_

---

<div class="post-metadata">

**Author:** ![Drew\_Olson](https://avatars.discourse-cdn.com/v4/letter/d/c67d28/32.png) [@Drew\_Olson](https://rubytalk.org/u/Drew_Olson)\
**Post date:** [16 July 2007 15:31 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/18 "2007-07-16T15:31:45Z")

</div>

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

&nbsp;&nbsp;alias :orig\_to\_s :to\_s

&nbsp;&nbsp;# sum the integer values of array contents  
&nbsp;&nbsp;def int\_sum  
&nbsp;&nbsp;&nbsp;&nbsp;self.inject(0){|sum,i| sum+i.to\_i}  
&nbsp;&nbsp;end

&nbsp;&nbsp;# find the maximum sub array in an array  
&nbsp;&nbsp;def max\_sub\_array  
&nbsp;&nbsp;&nbsp;&nbsp;(0...self.size).inject([self.first]) do |max\_sub,i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(i...self.size).each do |j|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if max\_sub.int\_sum \< self[i..j].int\_sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max\_sub = self[i..j]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max\_sub  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

&nbsp;&nbsp;# pretty printing for array  
&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;self.inject("[") do |str,i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;str + "#{i}, "  
&nbsp;&nbsp;&nbsp;&nbsp;end[0...-2] + "]"  
&nbsp;&nbsp;end  
end

# test example  
if \_\_FILE\_\_ == $0  
&nbsp;&nbsp;my\_arr = [-1, 2, 5, -1, 3, -2, 1]  
&nbsp;&nbsp;puts "array: #{my\_arr}"  
&nbsp;&nbsp;puts "maximum sub-array: #{my\_arr.max\_sub\_array}"  
end

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

---

<div class="post-metadata">

**Author:** ![James\_Koppel](https://avatars.discourse-cdn.com/v4/letter/j/0ea827/32.png) [@James\_Koppel](https://rubytalk.org/u/James_Koppel)\
**Post date:** [16 July 2007 22:19 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/19 "2007-07-16T22:19:03Z")

</div>

Solution #1: Array is bound to arr  
&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;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  
&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;Solution #2: Array is bound to a  
&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;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]

> **···**
>
> ---------------------------------  
> Now that's room service! Choose from over 150,000 hotels  
> in 45,000 destinations on Yahoo! Travel to find your fit.

---

<div class="post-metadata">

**Author:** ![Harry3](https://avatars.discourse-cdn.com/v4/letter/h/54ee81/32.png) [@Harry3](https://rubytalk.org/u/Harry3)\
**Post date:** [18 July 2007 03:21 UTC](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080/20 "2007-07-18T03:21:09Z")

</div>

> Extra Credit:
> 
> Given a matrix of integers, find the rectangle with maximum sum.

> **···**
>
> On 7/13/07, Ruby Quiz \<james@grayproductions.net\> wrote:  
> #  
> # 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|  
> &nbsp;&nbsp;(0...mat.column\_size).each do |b|  
> &nbsp;&nbsp;&nbsp;&nbsp;(1..mat.row\_size).each do |x|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(1..mat.column\_size).each do |y|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s \<\< mat.minor(a,x,b,y)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;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  
> &nbsp;&nbsp;x.each {|y| print y.map{|m| m.to\_s.rjust(tot.flatten.max.to\_s.length+2)},"\n"}  
> end
> 
> # Harry
> 
> --  
> A Look into Japanese Ruby List in English
> 
> > **[Kakueki.com is for sale | HugeDomains](https://www.hugedomains.com/domain_profile.cfm?d=kakueki.com)**
> >
> > Start using this domain right away. Straightforward domain shopping experience. Quick access to your domain.

[Next page](https://rubytalk.org/t/quiz-maximum-sub-array-131/39080.md?page=2)