AVGSCORE - Editorial

[daga_07]

PROBLEM LINK: Contest

Practice

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₁*A₁ + x₂*A₂ + … + x_nA_n, where x_i = 1 or -1. Also it can be easily inferred that x₁ = 1 because A₁ is never followed by a minus sign. Also A₂ will pair with A₁ as (A₁ - A₂), after that there will be no change in sign of A₂. So x₂ 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₃*A₃ + x₄*A₄ + … + x_nA_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₁-A₂+A₃+A₄+…+A_n.

TIME COMPLEXITY

O(N)

SOLUTION

Code