Velocity Reviews > Re: Puzzle

# Re: Puzzle

Arthur J. O'Dwyer
Guest
Posts: n/a

 07-30-2003

On Wed, 30 Jul 2003, Joona I Palaste wrote:
>
> Ramgopal <(E-Mail Removed)> scribbled the following:
> > You're given an array containing both positive and negative integers
> > and required to find the sub-array with the largest sum (O(N) a la
> > KBL). Write a routine in C for the above.

>
> Umm, call me stupid, but wouldn't just iterating once over the array,
> picking up every positive number and no negative numbers do? Or are we
> talking *contiguous* sub-arrays here?

"Sub-array" implies "contiguous," yes. Still, one iteration will do.
Possibly bogus hint: It might help to think of the array

1 2 3 -2 -3 6 1 -1 4 5
as
6 -5 7 -1 9

for the purposes of this assignment.

-Arthur

Martin Ambuhl
Guest
Posts: n/a

 07-30-2003
Arthur J. O'Dwyer wrote:

> "Sub-array" implies "contiguous," yes. Still, one iteration will do.
> Possibly bogus hint: It might help to think of the array
>
> 1 2 3 -2 -3 6 1 -1 4 5
> as
> 6 -5 7 -1 9
>
> for the purposes of this assignment.

Or as 6 <skip> 7 <skip> 9

Arthur J. O'Dwyer
Guest
Posts: n/a

 07-30-2003

On Wed, 30 Jul 2003, Martin Ambuhl wrote:
>
> Arthur J. O'Dwyer wrote:
>
> > "Sub-array" implies "contiguous," yes. Still, one iteration will do.
> > Possibly bogus hint: It might help to think of the array
> >
> > 1 2 3 -2 -3 6 1 -1 4 5
> > as
> > 6 -5 7 -1 9
> >
> > for the purposes of this assignment.

>
> Or as 6 <skip> 7 <skip> 9

What good would that do? The max-valued sub-array in this case
is the whole array. How does your method (whatever it is) distinguish
between 6 -5 7 -1 9 and 6 -7 7 -1 9 ?

This is not a completely trivial puzzle. I might expect to see it
as the first or second problem in a USACO contest, actually. I haven't
worked out the details because it doesn't strike my fancy at the
moment, but I'm sure the OP *could* do it if he cared to.

-Arthur

Kevin D. Quitt
Guest
Posts: n/a

 07-30-2003
On Wed, 30 Jul 2003 09:40:58 -0400 (EDT), "Arthur J. O'Dwyer"
<(E-Mail Removed)> wrote:
>
> 1 2 3 -2 -3 6 1 -1 4 5
>as
> 6 -5 7 -1 9
>

Doesn't the sub-array 7 -1 9 have a larger sum? And for that matter, the
sub-array 6 -5 7 -1 9 is the largest. Or are the sub-arrays only supposed
to hold positive numbers?

--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list

Arthur J. O'Dwyer
Guest
Posts: n/a

 07-30-2003

On Wed, 30 Jul 2003, Kevin D. Quitt wrote:
>
> On Wed, 30 Jul 2003 09:40:58 -0400 (EDT), "Arthur J. O'Dwyer"
> <(E-Mail Removed)> wrote:
> >
> > 1 2 3 -2 -3 6 1 -1 4 5
> >as
> > 6 -5 7 -1 9
> >

>
> Doesn't the sub-array 7 -1 9 have a larger sum?

7 -1 + 9 = 15
6 -5 + 7 -1 + 9 = 1 + 15 = 16

> And for that matter, the
> sub-array 6 -5 7 -1 9 is the largest.

"Largest" in the sense of "longest", I suppose?
Yes, but the OP asked for the sub-array with the
maximal sum. (In this case it's the same thing.)
I just didn't bother to phrase the problem as nicely

> Or are the sub-arrays only supposed
> to hold positive numbers?

Not at all.

-Arthur

Carsten Hansen
Guest
Posts: n/a

 07-30-2003

"Joona I Palaste" <(E-Mail Removed)> wrote in message
news:bg8r7s\$mhu\$(E-Mail Removed)...
> Arthur J. O'Dwyer <(E-Mail Removed)> scribbled the following:
> > On Wed, 30 Jul 2003, Joona I Palaste wrote:
> >> Ramgopal <(E-Mail Removed)> scribbled the following:
> >> > You're given an array containing both positive and negative integers
> >> > and required to find the sub-array with the largest sum (O(N) a la
> >> > KBL). Write a routine in C for the above.
> >>
> >> Umm, call me stupid, but wouldn't just iterating once over the array,
> >> picking up every positive number and no negative numbers do? Or are we
> >> talking *contiguous* sub-arrays here?

>
> > "Sub-array" implies "contiguous," yes. Still, one iteration will do.
> > Possibly bogus hint: It might help to think of the array

>
> > 1 2 3 -2 -3 6 1 -1 4 5
> > as
> > 6 -5 7 -1 9

>
> > for the purposes of this assignment.

>
> I figured out an O(n) way to solve the problem while lying on the
> rocky surface of Torra Lövö, Espoo. Here's the general idea:
> When encountering a positive number, add it to your working sum.
> When encountering a negative number, zero your working sum.
> When encountering any number, check if your working sum is greater
> than the greatest sum found so far.
> After checking all the numbers, the greatest sum found so far should
> be the greatest sum there is.
> Adding a number to a sum, zeroing the sum, and comparing two sums are
> each O(1) operations, so the total time should be O(n).
> It is left as an exercise for the OP to implement this in C.
>
> --
> /-- Joona Palaste ((E-Mail Removed)) ---------------------------\
> | Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
> | http://www.helsinki.fi/~palaste W++ B OP+ |
> \----------------------------------------- Finland rules! ------------/
> "No, Maggie, not Aztec, Olmec! Ol-mec!"
> - Lisa Simpson

Take the sequence 1, 2, 3, -2, -3, 6, 1, -1, 4, 5.

working sum greatest sum
0 0
1 1 1
2 3 3
3 6 6
-2 0 6
-3 0 6
6 6 6
1 7 7
-1 0 7
4 4 7
5 9 9

However the correct maximal sum is 16, the sum of all the numbers.

Carsten Hansen

Kevin Easton
Guest
Posts: n/a

 07-30-2003
Joona I Palaste <(E-Mail Removed)> wrote:
> Arthur J. O'Dwyer <(E-Mail Removed)> scribbled the following:
>> On Wed, 30 Jul 2003, Joona I Palaste wrote:
>>> Ramgopal <(E-Mail Removed)> scribbled the following:
>>> > You're given an array containing both positive and negative integers
>>> > and required to find the sub-array with the largest sum (O(N) a la
>>> > KBL). Write a routine in C for the above.
>>>
>>> Umm, call me stupid, but wouldn't just iterating once over the array,
>>> picking up every positive number and no negative numbers do? Or are we
>>> talking *contiguous* sub-arrays here?

>
>> "Sub-array" implies "contiguous," yes. Still, one iteration will do.
>> Possibly bogus hint: It might help to think of the array

>
>> 1 2 3 -2 -3 6 1 -1 4 5
>> as
>> 6 -5 7 -1 9

>
>> for the purposes of this assignment.

>
> I figured out an O(n) way to solve the problem while lying on the
> rocky surface of Torra L?v?, Espoo. Here's the general idea:
> When encountering a positive number, add it to your working sum.
> When encountering a negative number, zero your working sum.
> When encountering any number, check if your working sum is greater
> than the greatest sum found so far.
> After checking all the numbers, the greatest sum found so far should
> be the greatest sum there is.

That doesn't work - consider:

int a[] = { -100, 200, -10, 1, -10, 200, -1000, 300 };

The maximum subarray is { 200, -10, 1, -10, 200 } but your algorithm
will zero out the sum at the first -10, so it will return { 300 } as the
maximum subarray.

- Kevin.

> Adding a number to a sum, zeroing the sum, and comparing two sums are
> each O(1) operations, so the total time should be O(n).
> It is left as an exercise for the OP to implement this in C.
>

MG
Guest
Posts: n/a

 07-31-2003

"Arthur J. O'Dwyer" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
>
> On Wed, 30 Jul 2003, Martin Ambuhl wrote:
> >
> > Arthur J. O'Dwyer wrote:
> >
> > > "Sub-array" implies "contiguous," yes. Still, one iteration will do.
> > > Possibly bogus hint: It might help to think of the array
> > >
> > > 1 2 3 -2 -3 6 1 -1 4 5
> > > as
> > > 6 -5 7 -1 9
> > >
> > > for the purposes of this assignment.

> >
> > Or as 6 <skip> 7 <skip> 9

>
> What good would that do? The max-valued sub-array in this case
> is the whole array. How does your method (whatever it is) distinguish
> between 6 -5 7 -1 9 and 6 -7 7 -1 9 ?
>
> This is not a completely trivial puzzle. I might expect to see it
> as the first or second problem in a USACO contest, actually. I haven't
> worked out the details because it doesn't strike my fancy at the
> moment, but I'm sure the OP *could* do it if he cared to.

how abt this as the solution:

u need to add the m number starting from index 0, and keep a track of the
sum and the index of the substring corresponding to that sum...
then use sliding window protocol...and at each step...compare the values of
the sum...and update the sum and the index pointer as required.....

by the end of the loop...u know the index of the sub aray which has the
maximum sum..

Glen Herrmannsfeldt
Guest
Posts: n/a

 07-31-2003

"Kevin Easton" <(E-Mail Removed)> wrote in message
news:newscache\$4q2vih\$ht1\$(E-Mail Removed)...

(snip)

> >> "Sub-array" implies "contiguous," yes. Still, one iteration will do.
> >> Possibly bogus hint: It might help to think of the array

> >
> >> 1 2 3 -2 -3 6 1 -1 4 5
> >> as
> >> 6 -5 7 -1 9

> >
> >> for the purposes of this assignment.

> >
> > I figured out an O(n) way to solve the problem while lying on the
> > rocky surface of Torra L?v?, Espoo. Here's the general idea:
> > When encountering a positive number, add it to your working sum.
> > When encountering a negative number, zero your working sum.
> > When encountering any number, check if your working sum is greater
> > than the greatest sum found so far.
> > After checking all the numbers, the greatest sum found so far should
> > be the greatest sum there is.

>
> That doesn't work - consider:
>
> int a[] = { -100, 200, -10, 1, -10, 200, -1000, 300 };
>
> The maximum subarray is { 200, -10, 1, -10, 200 } but your algorithm
> will zero out the sum at the first -10, so it will return { 300 } as the
> maximum subarray.

Add each number to the working sum. When the working sum goes negative, set
it to zero.

If you want the begin and end points, reset the begin point when the sum
goes negative or zero. Save the begin point with the end point when a new,
higher working sum is found.

Google for "smith waterman" will probably find an algorithm that does this.

-- glen

Kevin Easton
Guest
Posts: n/a

 07-31-2003
MG <(E-Mail Removed)> wrote:
>
> "Glen Herrmannsfeldt" <(E-Mail Removed)> wrote in message
> news:cr2Wa.16506\$cF.7542@rwcrnsc53...

[...]
>> Add each number to the working sum. When the working sum goes negative,

> set
>> it to zero.
>>

> what abt the case when the array is all negative?????

Then the subarray with the maximum sum is the subarray consisting of
no elements (sum zero).

- Kevin.