add 1005

fishercoder1534 · fishercoder1534 · commit d00895a63b48 · 2019-12-24T07:07:38.000-08:00
diff --git a/README.md b/README.md
@@ -75,6 +75,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1010|[Pairs of Songs With Total Durations Divisible by 60](https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1010.java) | |Easy|
 |1009|[Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1009.java) | |Easy|
 |1008|[Construct Binary Search Tree from Preorder Traversal](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1008.java) | |Medium| Recursion
+|1005|[Maximize Sum Of Array After K Negations](https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1005.java) |  |Easy|
 |1003|[Check If Word Is Valid After Substitutions](https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1003.java) | |Medium|
 |1002|[Find Common Characters](https://leetcode.com/problems/find-common-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1002.java) |  |Easy|
 |999|[Available Captures for Rook](https://leetcode.com/problems/available-captures-for-rook/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_999.java) | |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_1005.java b/src/main/java/com/fishercoder/solutions/_1005.java
@@ -0,0 +1,72 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+import java.util.PriorityQueue;
+
+/**
+ * 1005. Maximize Sum Of Array After K Negations
+ *
+ * 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
+ * */
+public class _1005 {
+    public static class Solution1 {
+        /**credit: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252228/A-very-simple-java-solution*/
+        public int largestSumAfterKNegations(int[] A, int K) {
+            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
+            for (int num : A) {
+                minHeap.offer(num);
+            }
+            while (K-- > 0) {
+                minHeap.offer(-minHeap.poll());
+            }
+            int sum = 0;
+            while (!minHeap.isEmpty()) {
+                sum += minHeap.poll();
+            }
+            return sum;
+        }
+    }
+
+    public static class Solution2 {
+        /**credit: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252254/JavaC%2B%2BPython-Sort*/
+        public int largestSumAfterKNegations(int[] A, int K) {
+            Arrays.sort(A);
+            for (int i = 0; i < A.length && K > 0 && A[i] < 0; i++, K--) {
+                A[i] = -A[i];
+            }
+            int sum = 0;
+            int min = Integer.MAX_VALUE;
+            for (int i = 0; i < A.length; i++) {
+                min = Math.min(min, A[i]);
+                sum += A[i];
+            }
+            return K % 2 == 0 ? sum : sum - min * 2;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1005Test.java b/src/test/java/com/fishercoder/_1005Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1005;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1005Test {
+    private static _1005.Solution1 solution1;
+    private static _1005.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1005.Solution1();
+        solution2 = new _1005.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(5, solution1.largestSumAfterKNegations(new int[]{4, 2, 3}, 1));
+        assertEquals(5, solution2.largestSumAfterKNegations(new int[]{4, 2, 3}, 1));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(6, solution1.largestSumAfterKNegations(new int[]{3, -1, 0, 2}, 3));
+        assertEquals(6, solution2.largestSumAfterKNegations(new int[]{3, -1, 0, 2}, 3));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(13, solution1.largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));
+        assertEquals(13, solution2.largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(22, solution1.largestSumAfterKNegations(new int[]{-8, 3, -5, -3, -5, -2}, 6));
+        assertEquals(22, solution2.largestSumAfterKNegations(new int[]{-8, 3, -5, -3, -5, -2}, 6));
+    }
+}
