Re: Puzzle

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

  1. 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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. 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
    #3
  4. 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
    #4
  5. 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

    Draw your own conclusions.

    > 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
    in my reply.

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


    Not at all.

    -Arthur
     
    Arthur J. O'Dwyer, Jul 30, 2003
    #5
  6. "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
    #6
  7. Arthur J. O'Dwyer

    Kevin Easton Guest

    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
    #7
  8. Arthur J. O'Dwyer

    MG Guest

    "Arthur J. O'Dwyer" <> wrote in message
    news:p...
    >
    > 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
    #8
  9. "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
    #9
  10. Arthur J. O'Dwyer

    Kevin Easton Guest

    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
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Earl Teigrob
    Replies:
    3
    Views:
    6,652
    Nedu N
    Aug 6, 2003
  2. dwa

    Design Puzzle!

    dwa, Jun 10, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    369
    Cowboy \(Gregory A. Beamer\) [MVP]
    Jun 10, 2004
  3. Shankara Narayanan

    Booking puzzle....

    Shankara Narayanan, Jun 17, 2004, in forum: ASP .Net
    Replies:
    20
    Views:
    931
    bredal Jensen
    Jun 30, 2004
  4. VB Programmer
    Replies:
    2
    Views:
    430
    Alan Lambert
    Nov 4, 2004
  5. G. Stewart

    regex puzzle!

    G. Stewart, Nov 23, 2004, in forum: ASP .Net
    Replies:
    8
    Views:
    518
    G. Stewart
    Nov 25, 2004
Loading...

Share This Page