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 <= A.length <= 100001 <= K <= 10000-100 <= A[i] <= 100struct 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);
}