luoheng
10/27/2019 - 10:24 AM

largestSumAfterKNegations

func largestSumAfterKNegations(A []int, K int) int {
    c := [201]int{}
    for _, a := range A {
        c[a+100]++ 
    }
    for i := 0; i < 100; i++ {
        if K == 0 {
            break
        }
        if c[i] > 0 {
            if K >= c[i] {
                c[200-i] += c[i]
                K -= c[i]
                c[i] = 0
            } else {
                c[200-i] += K
                c[i] -= K
                K = 0
            }
        }
    }
    for i := 100; i <= 200; i++ {
        if K == 0 {
            break
        }
        if c[i] > 0 {
            if K % 2 != 0 {
                c[i] -= 1
                c[200-i] += 1
            }
            K = 0
        }
    }
    sum := 0
    for i := 0; i < 201; i++ {
        sum += c[i] * (i - 100)
    }
    return sum
}