# PROBLEM LINK: Contest

**Author:** Vaibhav Daga

## DIFFICULTY

Easy

## PREREQUISITES

None

## PROBLEM

Given an array pick two elements A_{i} and A_{i+1} and replace them with A_{i} - A_{i+1}. Repeat the steps until array is left with one element. Maximise the last element left.

## EXPLANATION

Observe that the final element can be written as x_{1}*A_{1} + x_{2}*A_{2} + … + x_{n}A_{n}, where x_{i} = 1 or -1. Also it can be easily inferred that x_{1} = 1 because A_{1} is never followed by a minus sign. Also A_{2} will pair with A_{1} as (A_{1} - A_{2}), after that there will be no change in sign of A_{2}. So x_{2} will always be -1. All other values of x_{i} for i>2, can take both 1 and -1 values. To maximize the value of last element left, the value x_{3}*A_{3} + x_{4}*A_{4} + … + x_{n}A_{n} should be as large as possible. Since all A_{i}’s are positive, the value of x_{i} must be equal to 1. So the maximum value of last element equals A_{1}-A_{2}+A_{3}+A_{4}+…+A_{n}.

## TIME COMPLEXITY

**O(N)**