Maximum Sub-Array (#131)

bbazzarrakk · July 13, 2007, 4:35pm

The three rules of Ruby Q.:

Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.
Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For
example:

array: [-1, 2, 5, -1, 3, -2, 1]
maximum sub-array: [2, 5, -1, 3]

Extra Credit:

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

bbazzarrakk · July 13, 2007, 4:49pm

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

bbazzarrakk · July 13, 2007, 4:51pm

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

bbazzarrakk · July 13, 2007, 5:58pm

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.

bbazzarrakk · July 13, 2007, 6:29pm

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

bbazzarrakk · July 13, 2007, 6:46pm

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?

bbazzarrakk · July 15, 2007, 4:40pm

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

bbazzarrakk · July 15, 2007, 4:42pm

On Fri, 13 Jul 2007 23:29:03 +0900, Ruby Q. wrote:

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone on Ruby T. follow the discussion. Please reply to the
original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For
example:

array: [-1, 2, 5, -1, 3, -2, 1] maximum sub-array:
[2, 5,
-1, 3]

Extra Credit:

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

#!/usr/bin/env ruby

require ‘matrix’

#strangely, none of these methods are in the facets gem.

module Enumerable
def argmax
curmax=nil
curval=nil
each do |x|
t=yield x
if not curmax or (curmax < t)
curmax=t
curval=x
end
end
curval
end

def sum
inject{|a,b|a+b}
end

def subarrays
result=[]
(0…length).each do |start|
((start + 1)…length).each do |finish|
result << self[start…finish]
end
end
result
end
end

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}

bbazzarrakk · July 15, 2007, 4:48pm

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

bbazzarrakk · July 15, 2007, 5:32pm

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

bbazzarrakk · July 15, 2007, 5:34pm

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

bbazzarrakk · July 15, 2007, 5:46pm

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

bbazzarrakk · July 15, 2007, 5:47pm

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.

bbazzarrakk · July 15, 2007, 5:55pm

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

bbazzarrakk · July 15, 2007, 5:57pm

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

bbazzarrakk · July 15, 2007, 4:50pm

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

bbazzarrakk · July 15, 2007, 7:48pm

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

Doesn’t this basically make it order n cubed?

bbazzarrakk · July 15, 2007, 11:05pm

No extra credit on this one, but my solution handles a regular list of
numbers just fine.
First, I created an object to define a range of numbers:

Object defining a sub-array of integer values

The sub-array contains a start and end index

defining a region of the master array

class SubArray
def initialize
@start = 0
@end = 0
@sum = 0
end

Set boundaries of the sub-array

def set_bounds(list_start, list_end)
@start, @end = list_start, list_end
end

Provide get/set accessors

attr_reader :start, :end, :sum
attr_writer :sum
end

Then I created a class to find the sub-array with the maximum sum.
Basically
it performs a single pass of the array, updating the maximum sub-array
each
time the current sum exceeds the current maximum sum:

class MaxSubArray

Finds the sub-array with the largest sum

Input: a list of integers

def find(list)
max = SubArray.new
cur = SubArray.new

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

  if (cur.sum > max.sum)
    max.sum = cur.sum
    cur.set_bounds(cur.start, i)
    max.set_bounds(cur.start, i)
  elsif (cur.sum < 0)
    # If sum goes negative, this region cannot have the max sum
    cur.sum = 0
    cur.set_bounds(i + 1, i + 1)
  end
end

list.slice(max.start, max.end - max.start + 1)

end
end

And finally, here are some tests:

$:.unshift File.join(File.dirname(FILE), “…”)
require ‘test/unit’
require ‘max_sub_array.rb’

class TestMaxSubArray < Test::Unit::TestCase
def setup
@ma = MaxSubArray.new
end

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

Thanks,

Justin

bbazzarrakk · July 16, 2007, 2:07am

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

bbazzarrakk · July 16, 2007, 3:09am

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