PROBLEM LINK: Contest
Author: Vaibhav Daga
Given an array pick two elements Ai and Ai+1 and replace them with Ai - Ai+1. Repeat the steps until array is left with one element. Maximise the last element left.
Observe that the final element can be written as x1*A1 + x2*A2 + … + xnAn, where xi = 1 or -1. Also it can be easily inferred that x1 = 1 because A1 is never followed by a minus sign. Also A2 will pair with A1 as (A1 - A2), after that there will be no change in sign of A2. So x2 will always be -1. All other values of xi for i>2, can take both 1 and -1 values. To maximize the value of last element left, the value x3*A3 + x4*A4 + … + xnAn should be as large as possible. Since all Ai’s are positive, the value of xi must be equal to 1. So the maximum value of last element equals A1-A2+A3+A4+…+An.