Problem - Maximize Sum of Array After K Negations

Given an array and integer $k$, choose an index and negate the value. Do this $k$ times to maximize the sum. For $A = [4,2,3]$, $k = 1$, negate nothing (or negate and un-negate). Max sum is $9$. For $A = [3,-1,0,2]$, $k = 3$, negate $-1$ three times (or negate it once, then negate $0$ twice). Answer is $6$.

Think about which elements you should negate and in what order. Constraint: you must use exactly $k$ negations, even if it means negating the same element multiple times.

If all numbers are positive and $k$ is odd, you will end up with one negative number. The goal is to minimize the absolute value of that final negative.