The greedy insight: always negate the smallest element.
If there are negative numbers, negate the most negative first (it becomes the largest positive contribution).
If all numbers are non-negative and you have remaining flips, repeatedly negate the smallest (which might be ). Sort the array. Negate from the smallest.
If you run out of negatives and have odd remaining flips, negate the smallest positive once. Why this works: negating the smallest (most negative) number gives the largest increase in sum.