// Runtime: 52 ms, faster than 99.29% of JavaScript online submissions for Maximize Sum Of Array After K Negations.
// Memory Usage: 35 MB, less than 100.00% of JavaScript online submissions for Maximize Sum Of Array After K Negations.

var largestSumAfterKNegations = function(numbers, k) {
    let negative = []
    let minAbs = null
    let sum = 0
    numbers.forEach(item => {
        if (item < 0) {
            negative.push(item)
        }
        if (minAbs === null || Math.abs(minAbs) > Math.abs(item)) {
            minAbs = item
        }
        sum += item
    })
    negative.sort((a, b) => a - b)
    while (negative.length && k) {
        sum -= negative.shift() * 2
        k--
    }
    if (k % 2) {
        sum -= Math.abs(minAbs) * 2
    }
    return sum
};