i starts from 1; Noticing that sum((-1^i) * v[i]) doesn't change overall, so we can construct b[i] = -1^i * v[i] and let the biggest ceil(n/2) elements be on the positive slot and then count the result
The ans would then be sum(positive half) + sum(negative half), as sum(negative half) = sum(b) — sum(positive half), so the answer is 2*sum(positive) — sum(b)
I don't get how people can think of such complicated answers during contest, The most logical way to think about it is that in order to change the sign of an element on an odd index you need to swap with an element of an even index and greedily keep swapping smallest elements of each group as long as you're getting +ve delta check my last submission.
yeah I agree, the solution you gave is far more intuitive