題目

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

題目大意

將數組中的元素變成它的相反數，這種操作執行 K 次之後，求出數組中所有元素的總和最大。

解題思路

這一題可以用最小堆來做，構建最小堆，每次將最小的元素變成它的相反數。然後最小堆調整，再將新的最小元素變成它的相反數。執行 K 次以後求數組中所有的值之和就是最大值。

這道題也可以用排序來實現。排序一次，從最小值開始往後掃，依次將最小值變為相反數。這裏需要注意一點，負數都改變成正數以後，接着不是再改變這些變成正數的負數，而是接着改變順序的正數。因為這些正數是比較小的正數。負數越小，變成正數以後值越大。正數越小，變成負數以後對總和影響最小。具體實現見代碼。 �具體實現見代碼。

參考代碼

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
}