# Maximum Sub-Array (#131)

The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

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

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 7/13/07, Matt G. [email protected] 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 Jul 13, 10:29 am, Ruby Q. [email protected] 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 Jul 13, 2007, at 10:42 AM, Paul N. 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 G. II

On 7/13/07, Matt G. [email protected] wrote:

On 7/13/07, Matt G. [email protected] 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?

Given a matrix of integers, find the rectangle with maximum sum.

# 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 Fri, 13 Jul 2007 23:29:03 +0900, Ruby Q. 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}

Ruby Q. wrote:

Given a matrix of integers, find the rectangle with maximum sum.

*# The algorithm for max_subarray is a slightly adapted version of

the same

# 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

x1 = 0

x2 = 0

running_max = 0

# 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)

# 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

running_max = 0

x1 = 0

x2 = 0

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}”
*

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 7/13/07, Ruby Q. [email protected] wrote:

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

them.

# 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

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

``` # 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 ```

Regards, Morton

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:

numbers,

into

to their

+,-,+,-,…,+

problem.

tried

indices.

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.

#!/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]

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

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

Morton G. wrote, On 7/15/2007 10:44 AM:

``` ```

Doesn’t this basically make it order n cubed?

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:

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

# 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

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 Jul 15, 2007, at 1:47 PM, Sammy L. wrote:

``````     sub = arry[i..j]
``````

result
end

Yes, the inject introduces another factor of N. I missed that.

Regards, Morton