1005. Maximize Sum Of Array After K Negations #

Problem #

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

Problem Summary #

Change elements in the array into their opposites. After performing this operation K times, find the maximum possible sum of all elements in the array.

Solution Approach #

This problem can be solved using a min-heap. Build a min-heap, and each time change the smallest element into its opposite. Then adjust the min-heap, and change the new smallest element into its opposite. After performing this K times, the sum of all values in the array is the maximum value.

This problem can also be implemented with sorting. Sort once, then scan backward starting from the minimum value, and sequentially change the minimum values into their opposites. One thing to note here is that after all negative numbers have been changed to positive numbers, you should not continue changing those negative numbers that have become positive; instead, continue changing the positive numbers in order. This is because these positive numbers are relatively small positive numbers. The smaller a negative number is, the larger its value becomes after being changed to positive. The smaller a positive number is, the smaller its impact on the total sum after being changed to negative. See the code for the specific implementation.

Code #

package leetcode

import (
	"sort"
)

func largestSumAfterKNegations(A []int, K int) int {
	sort.Ints(A)
	minIdx := 0
	for i := 0; i < K; i++ {
		A[minIdx] = -A[minIdx]
		if A[minIdx+1] < A[minIdx] {
			minIdx++
		}
	}
	sum := 0
	for _, a := range A {
		sum += a
	}
	return sum
}