Maximize Array Sum After K Negations

ArrayGreedySorting

Given an array of integers and a non-negative integer k, the task is to maximize the sum of the array after performing exactly k negations. A negation is defined as changing the sign of any array element. For each negation, choose any element of the array and switch it from positive to negative or from negative to positive.

Example 1

Input

[
  [
    3,
    -1,
    0,
    2
  ],
  3
]

Output

Explanation. Negate -1 to make it 1, negate 0 twice (which keeps it at 0). The sum becomes 3 + 1 + 0 + 2 = 6.

Example 2

Input

[
  [
    2,
    -3,
    4
  ],
  2
]

Output

Explanation. Negate -3 to make it 3 and no need for the second negation as it won't increase the sum. The sum becomes 2 + 3 + 4 = 9.

Example 3

Input

[
  [
    -2,
    5,
    0,
    -1
  ],
  4
]

Output

Explanation. We can negate -2 to get 2 and negate -1 to get 1. We then negate 0 twice (remains 0). The sum is 2 + 5 + 0 + 1 = 8.

Follow-up: Can you solve this in O(n log n) time complexity using a priority queue or other efficient method?

Constraints:

1. The length of the array is between 1 and 10000. 2. Each element in the array will be between -100 and 100. 3. `k` is a non-negative integer.

Views: 3