Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Here is your original set

3 2 8 9 -25 5 8 4 4 -3 5 3 -10

First step is adding up consequitive positives and consequitive negatives. The reason for adding up consequitive positives is crystal clear. The only reason, you may pick a negative at any time is it may bring a positive value in future if we keep on going to right. Therefore, to go right and reach a positive value, you must pass through all negatives in the sequence which are in a row. I've made this simplification to see the big picture
Here is the set after this process

22 -25 21 -3 8 -10

At this point, I will start from the end of list, and go to the beginning of list while keeping LOCAL BENEFIT and CURRENT MAX. If the end of list is negative, I will skip it and go left. Otherwise, I will assume it is current maximum that I can reach.

At this point, 8 is assumed to be current maximum, and local benefit is 0.

At the next step, I will update local benefit by adding 8, and -3, and assign it +5. Then my current position will be 21 with this local benefit +5. The current position will take the local benefit if it is positive, or drop it if it is negative or 0. If the current position accepts the local benefit, it will add itself with the local benefit, so 21 + 5 =26 which is now bigger than current maximum, so current maximum will start from the position of 21. If the local benefit is 0 or negative, it will be assigned to 0, and re-calculated from the current position, and its negative value neighbor on its left. If the local benefit is positive, the difference between current position ,and negative neighbor on left will be added up to local benefit. If you follow the procedure above, and reach the last positive on the left, you have done the complete assetment.

Here is the algorithm applied to data set.

22 -25 21 -3 8 -10

-10 droped firstly from the end.

current pos : 8 - current max : 8 - local benefit : 0

STEP 2:

current pos : 21 - current max : 8 - local benefit : 5

21 + 5 = 26 > 8, so update current max

current pos : 21 - current max : 26

STEP 3:

current pos : 22-current max : 26-local benefit : -25+26 =1

22 + 1 = 23 < 26

so current max doesn't change, and local benefit becomes 23 since 0 + 22 + 1 .

Here ( 0 + 22 ) is the value adding up to local benefit. However, since there is no value on left, it becomes 0 instead oa negative neighbor.

The algorithm complexity is linear. The first step is for reduction, and takes linear space and time. However, it is there just reduce the problem size.

The real solution is also linear since you travse from the end of list to the begining while keeping contant extra storage space.

Ok guys, there is the outline of my algorithm


In reply to Re: Largest Sum of Consecutive Integers by Anonymous Monk
in thread Largest Sum of Consecutive Integers by OverlordQ

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others browsing the Monastery: (5)
    As of 2017-12-15 01:05 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      What programming language do you hate the most?




















      Results (415 votes). Check out past polls.

      Notices?