Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: Largest Sum of Consecutive Integers

by Anonymous Monk
on Oct 13, 2008 at 19:30 UTC ( [id://716842]=note: print w/replies, xml ) Need Help??


in reply to Largest Sum of Consecutive Integers

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

Replies are listed 'Best First'.
Re^2: Largest Sum of Consecutive Integers
by Anonymous Monk on Oct 13, 2008 at 20:29 UTC
    Hi Every One,

    I have improved my algorithm going from back to forward, but this time it also goes from left to right.

    You keep a current max, and current sum

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

    current sum 3 5 13 22 0 5 13 17 21 18 23 26 16

    current max 3 5 13 22 22 22 22 22 22 22 23 26 26

    When I reach -25. I update current sum and it is negtiave, so I start the current sum from here again from scratch.

    This method can even accept infinite numbers coming from an outside source, so it is on the fly algorithm which uses greedy methods

    Ilteris Murat Derici & David Matula

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://716842]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having an uproarious good time at the Monastery: (6)
As of 2024-03-28 14:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found