|
|
|
| laziness, impatience, and hubris | |
| PerlMonks |
comment on |
| ( [id://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
|
|