Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.org

README.org

Leetcode: Maximize Sum Of Array After K Negations


Maximize Sum Of Array After K Negations


Similar Problems:


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
  • 1 <= K <= 10000
  • -100 <= A[i] <= 100

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// https://code.dennyzhang.com/maximize-sum-of-array-after-k-negations
// Basic Ideas: array + greedy
//
// Complexity: Time O(n*log(n)), Space O(1)
import "sort"
func largestSumAfterKNegations(A []int, K int) int {
    sort.Ints(A)
    for i, v := range A {
        if K<=0 || v >= 0 {
            break
        }
        A[i] = -A[i]
        K--
    }
    minAbs := 1<<31-1
    sum := 0
    for _, v := range A {
        if v>=0 && v < minAbs {
            minAbs = v
        }
        sum += v
    }
    if K%2 == 1 {
        sum -= 2*minAbs
    }
    return sum
}
linkedin
github
slack
You can’t perform that action at this time.