K Negations - Implementation

Here is the solution:

function largestSumAfterKNegations(A, k)
 sort A ascending
 i := 0
 while k > 0 and i < length and A[i] < 0
 A[i] := -A[i]
 i := i + 1
 k := k - 1
 if k % 2 = 1 then
 minVal := min(A)
 sum := sum(A) - 2 * minVal
 return sum
 return sum(A)

Time: $O(n \log n)$. Space: $O(1)$.

Flip all negatives first. If odd flips remain, subtract twice the smallest (one flip changes it from $+x$ to $-x$, a difference of $2x$).