# Forum: Ruby Maximum Sub-Array (#131)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
on 2007-07-13 16:35
```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
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: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
> 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:

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_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.

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]```
This topic is locked and can not be replied to.