add 1746

fishercoder1534 · fishercoder1534 · commit 2f3c19d35d17 · 2021-02-28T19:02:40.000-08:00
diff --git a/README.md b/README.md
@@ -25,6 +25,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1750|[Minimum Length of String After Deleting Similar Ends](https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1750.java) ||Medium|Two Pointers|
 |1749|[Maximum Absolute Sum of Any Subarray](https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1749.java) ||Medium|Greedy|
 |1748|[Sum of Unique Elements](https://leetcode.com/problems/sum-of-unique-elements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1748.java) ||Easy|Array, HashTable|
+|1746|[Maximum Subarray Sum After One Operation](https://leetcode.com/problems/maximum-subarray-sum-after-one-operation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1746.java) ||Medium|DP|
 |1745|[Palindrome Partitioning IV](https://leetcode.com/problems/palindrome-partitioning-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1745.java) ||Hard|String, DP|
 |1743|[Restore the Array From Adjacent Pairs](https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1743.java) ||Medium|Greedy|
 |1742|[Maximum Number of Balls in a Box](https://leetcode.com/problems/maximum-number-of-balls-in-a-box/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1742.java) ||Easy|Array|
diff --git a/src/main/java/com/fishercoder/solutions/_1746.java b/src/main/java/com/fishercoder/solutions/_1746.java
@@ -0,0 +1,28 @@
+package com.fishercoder.solutions;
+
+public class _1746 {
+    public static class Solution1 {
+        /**
+         * credit: https://leetcode.com/problems/maximum-subarray-sum-after-one-operation/discuss/1049224/Java-O(n)-Time-O(n)-Space-DP-solution
+         */
+        public int maxSumAfterOperation(int[] nums) {
+            int len = nums.length;
+            //dp[i][0] means the sum of all elements in the subarray up to index i without any number squared
+            //dp[i][1] means the sum of all elements in the subarray up to index i with nums[i] squared
+            //esentially, there are three dimensions:
+            //1. the element nums[i] squared itself might be the biggest sum of subarray itself;
+            //2. the subarray sum without any elemtns squared + nums[i] squared
+            //3. the subarray sum with one element prior to i square + nums[i]
+            int[][] dp = new int[len][2];
+            dp[0][0] = nums[0];
+            dp[0][1] = nums[0] * nums[0];
+            int maxSum = dp[0][1];
+            for (int i = 1; i < len; i++) {
+                dp[i][0] = Math.max(dp[i - 1][0] + nums[i], nums[i]);
+                dp[i][1] = Math.max(nums[i] * nums[i], Math.max(dp[i - 1][0] + nums[i] * nums[i], dp[i - 1][1] + nums[i]));
+                maxSum = Math.max(maxSum, dp[i][1]);
+            }
+            return maxSum;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1746Test.java b/src/test/java/com/fishercoder/_1746Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1746;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1746Test {
+    private static _1746.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1746.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(17, solution1.maxSumAfterOperation(new int[]{2, -1, -4, -3}));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(4, solution1.maxSumAfterOperation(new int[]{1, -1, 1, 1, -1, -1, 1}));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(1936, solution1.maxSumAfterOperation(new int[]{-44}));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(10954
+                , solution1.maxSumAfterOperation(new int[]{29, 71, -52, -23, -28, 50, 27, 29, 0, 50,
+                        -92, 22, -38, 90, 3, 6, 70, -56, -7, 40, 79, 98, 72, 88, -5, -78, 12, 69, 30,
+                        -73, 99, -59, 33, 0, -6, 25, 87, -93, 20, -89, -22, 80, 57, 51, 48, 0, 65, -57,
+                        -57, 28, -42, -97, 97, -49, 38, 40, -41, 3, 31, -12, 47, -10, 17, -32, 68, 40,
+                        55, 86, -99, -2, 100, 89, 31, -67}));
+    }
+
+}
