_1005.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.Arrays;
importjava.util.PriorityQueue;

publicclass_1005 {
publicstaticclassSolution1 {
/*
 * credit: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252228/A-very-simple-java-solution
 */
publicintlargestSumAfterKNegations(int[] A, intK) {
PriorityQueue<Integer> minHeap = newPriorityQueue<>();
for (intnum : A) {
minHeap.offer(num);
 }
while (K-- > 0) {
minHeap.offer(-minHeap.poll());
 }
intsum = 0;
while (!minHeap.isEmpty()) {
sum += minHeap.poll();
 }
returnsum;
 }
 }

publicstaticclassSolution2 {
/*
 * credit: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252254/JavaC%2B%2BPython-Sort
 */
publicintlargestSumAfterKNegations(int[] A, intK) {
Arrays.sort(A);
for (inti = 0; i < A.length && K > 0 && A[i] < 0; i++, K--) {
A[i] = -A[i];
 }
intsum = 0;
intmin = Integer.MAX_VALUE;
for (inti = 0; i < A.length; i++) {
min = Math.min(min, A[i]);
sum += A[i];
 }
returnK % 2 == 0 ? sum : sum - min * 2;
 }
 }
}