---Grigor---'s blog

By ---Grigor---, 9 years ago, , This problem can be solved in linear time, using the following idea:
1. If desired prefix and suffix intersect, then their common part is remaining with the initial sign and
therefore, this case is equivalent to the case when we take the same suffix and prefix, but without their common part
:

(s1 [s2 )s3 ] is equal to (s1)s2[s3] (s1,s2,s3 - some subsequences).
2. Let the sum of elements A1 .. An be equal to S. Then when inverting signs we get -A1, -A2 .. -An, and the sum is thereafter changed to -S, i.e. sum of elements on the segment will just change its' sign when inverting the whole segment's signs.
3. One can consider the initial problem as follows: we have to choose a consecutive subsequence (the part of the initial sequence, remaining between suffix and prefix), and invert all the numbers remaining out of it. Considering the sum of the whole sequence be S, and the sum of the target subsequence as S1 , the total sum will be equal to -(S-S1) + S1 = 2*S1 - S  -  this is the value, we want to get. S is a constant, therefore to maximize this value, we just have to maximize S1, i.e. find a consecutive subsequence of the initial sequence that has the biggest sum, and this can be done in linear as follows:
mx = 0;
for(i=0;i<n;++i)
{
sum += a[i];
if(sum < 0)
sum = 0;
mx = max(mx, sum);
}    Comments (2)
 » 7 years ago, # | ← Rev. 2 →   can u please explain the third test case without telling me the approach to solve the question? i mean how o/p of third test case is 18?
•  » » Alternate only 1 element from beginning and only 1 element from end,then the sequence becomes 1 10 -5 10 2, the sum of which is 18.