[QUIZ] Maximum Sub-Array (#131)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

by Harlan

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

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

Extra Credit:

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

 

[Paul Novak]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

by Harlan

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

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

Extra Credit:

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

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.

 

[David Chelimsky]

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?

 

[David Chelimsky]

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]

Or this:

[1,2,3,-6,6]

options

[1,2,3]
[1,2,3,-6,6]
[6]

options:

[1,2,3]
[6]

Does it matter?

 

[Kyle Schmitt]

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

--Kyle

 

[Aureliano Calvo]

Am I missing something, or is this one of the easiest quizzes that's

been put forward?

Well, you're missing the fizzfuzz quiz.

 

[James Edward Gray II]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for
this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

by Harlan

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

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

Extra Credit:

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

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

Let's say we are looking for a non-empty subarray.

James Edward Gray II

 

[James Edward Gray II]

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?

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

 

[James Edward Gray II]

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

 

[Kyle Schmitt]

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

 

[Bob Showalter]

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

 

[anansi]

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?

 

[Ari Brown]

<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]. . [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.

 

[James Edward Gray II]

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]. . [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

 

[Ken Bloom]

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?

Because the subarrays in the quiz problem must be contiguous.

The answer to your proposed version is
ARRAY=[-1, 2, 5, -1, 3, -2, 1]
ARRAY.select{|x| x>=0}

--Ken

 

[Morton Goldberg]

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]. . [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

 

[Sammy Larbi]

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)

 

[Robert Dober]

Kyle Schmitt wrote, On 7/13/2007 11:10 AM:

Well, you could put a maximum time complexity constraint on it and the
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

 

[Ken Bloom]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until 48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

by Harlan

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

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

Extra Credit:

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

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

 

[Harry Kakueki]

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

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.

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