[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Maximum Sub-Array (#131

James Gray

7/13/2007 2:29:00 PM

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

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

Paul Novak

7/13/2007 3:38:00 PM

0

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

7/13/2007 3:56:00 PM

0

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?

David Chelimsky

7/13/2007 4:05:00 PM

0

On 7/13/07, David Chelimsky <dchelimsky@gmail.com> wrote:
> 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]

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

7/13/2007 4:11:00 PM

0

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

--Kyle

aurelianito

7/13/2007 4:26:00 PM

0

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

7/13/2007 4:26:00 PM

0

On Jul 13, 2007, at 10:42 AM, Paul Novak wrote:

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

7/13/2007 4:28:00 PM

0

On Jul 13, 2007, at 10:56 AM, David Chelimsky wrote:

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

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 Gray

7/13/2007 4:34:00 PM

0

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

Kyle Schmitt

7/13/2007 4:37:00 PM

0

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 7/13/07, Aureliano Calvo <aurelianocalvo@gmail.com> wrote:
> > Am I missing something, or is this one of the easiest quizzes that's
> > been put forward?
>
> Well, you're missing the fizzfuzz quiz.
>
>

Bob Showalter

7/13/2007 5:18:00 PM

0

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