Given an array and integer , choose an index and negate the value. Do this times to maximize the sum. For , , negate nothing (or negate and un-negate). Max sum is . For , , negate three times (or negate it once, then negate twice). Answer is .
Think about which elements you should negate and in what order. Constraint: you must use exactly negations, even if it means negating the same element multiple times.
If all numbers are positive and is odd, you will end up with one negative number. The goal is to minimize the absolute value of that final negative.