## 1005. Maximize Sum Of Array After K Negations

Given an array `A` of integers, we must modify the array in the following way: we choose an `i` and replace `A[i]` with `-A[i]`, and we repeat this process `K` times in total.  (We may choose the same index `i` multiple times.)

Return the largest possible sum of the array after modifying it in this way.

Example 1:

```Input: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].
```

Example 2:

```Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
```

Example 3:

```Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].
```

Note:

1. `1 <= A.length <= 10000`
2. `1 <= K <= 10000`
3. `-100 <= A[i] <= 100`

## Rust Solution

``````struct Solution;

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
fn largest_sum_after_k_negations(a: Vec<i32>, mut k: i32) -> i32 {
let reverse: Vec<Reverse<i32>> = a.into_iter().map(Reverse).collect();
let mut pq = BinaryHeap::from(reverse);
while k > 0 {
if let Some(min) = pq.pop() {
pq.push(Reverse(-min.0));
}
k -= 1;
}
pq.into_iter().map(|x| x.0).sum()
}
}

#[test]
fn test() {
let a = vec![4, 2, 3];
let k = 1;
assert_eq!(Solution::largest_sum_after_k_negations(a, k), 5);
let a = vec![3, -1, 0, 2];
let k = 3;
assert_eq!(Solution::largest_sum_after_k_negations(a, k), 6);
let a = vec![2, -3, -1, 5, -4];
let k = 2;
assert_eq!(Solution::largest_sum_after_k_negations(a, k), 13);
}
``````

Having problems with this solution? Click here to submit an issue on github.