Given an array of N integers. You can multiply at most K elements by -1. Find the maximum possible sum, of a subsequence of the modified array.
Claim: The optimal subsequence should only contain positive numbers present in the modified array.
(Proof is trivial and left to the reader as an exercise!)
Thus, It is optimal to multiply the negative numbers in the array by -1, making them positive (which can then be included in the optimal subsequence).
However, there might be more than K negative elements, all which we can’t multiply due to the given constraints.
Claim: It is optimal to multiply the K smallest negative numbers in the array, by -1.
If a < b, then -a > -b.
Thus, when a is negative, -a is positive and greater than -b, giving a larger sum when added to the subsequence.
Sort the array. Iterate from smallest to largest numbers, multiplying the first K negative elements by -1. Finally, iterate over the array once more, adding all the positive terms together, to get the required answer.
Sorting the array takes O(N\log N). Iterating over the array both times takes O(N) each. The total complexity is thus:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)