# Re: Puzzle

Discussion in 'C Programming' started by Arthur J. O'Dwyer, Jul 30, 2003.

1. ### Arthur J. O'DwyerGuest

On Wed, 30 Jul 2003, Joona I Palaste wrote:
>
> Ramgopal <> 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

Arthur J. O'Dwyer, Jul 30, 2003

2. ### Martin AmbuhlGuest

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

Martin Ambuhl, Jul 30, 2003

3. ### Arthur J. O'DwyerGuest

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

Arthur J. O'Dwyer, Jul 30, 2003
4. ### Kevin D. QuittGuest

On Wed, 30 Jul 2003 09:40:58 -0400 (EDT), "Arthur J. O'Dwyer"
<> 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

Kevin D. Quitt, Jul 30, 2003
5. ### Arthur J. O'DwyerGuest

On Wed, 30 Jul 2003, Kevin D. Quitt wrote:
>
> On Wed, 30 Jul 2003 09:40:58 -0400 (EDT), "Arthur J. O'Dwyer"
> <> 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

Arthur J. O'Dwyer, Jul 30, 2003
6. ### Carsten HansenGuest

"Joona I Palaste" <> wrote in message
news:bg8r7s\$mhu\$...
> Arthur J. O'Dwyer <> scribbled the following:
> > On Wed, 30 Jul 2003, Joona I Palaste wrote:
> >> Ramgopal <> 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 () ---------------------------\
> | 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

Carsten Hansen, Jul 30, 2003
7. ### Kevin EastonGuest

Joona I Palaste <> wrote:
> Arthur J. O'Dwyer <> scribbled the following:
>> On Wed, 30 Jul 2003, Joona I Palaste wrote:
>>> Ramgopal <> 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.
>

Kevin Easton, Jul 31, 2003
8. ### MGGuest

"Arthur J. O'Dwyer" <> wrote in message
news...
>
> 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..

MG, Jul 31, 2003
9. ### Glen HerrmannsfeldtGuest

"Kevin Easton" <> wrote in message
news:newscache\$4q2vih\$ht1\$...

(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

Glen Herrmannsfeldt, Jul 31, 2003
10. ### Kevin EastonGuest

MG <> wrote:
>
> "Glen Herrmannsfeldt" <> 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.

Kevin Easton, Jul 31, 2003