RUST GYM v0.2.11

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.