|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +/** |
| 4 | + * 1186. Maximum Subarray Sum with One Deletion |
| 5 | + * |
| 6 | + * Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. |
| 7 | + * In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element |
| 8 | + * left and the sum of the remaining elements is maximum possible. |
| 9 | + * Note that the subarray needs to be non-empty after deleting one element. |
| 10 | + * |
| 11 | + * Example 1: |
| 12 | + * Input: arr = [1,-2,0,3] |
| 13 | + * Output: 4 |
| 14 | + * Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value. |
| 15 | + * |
| 16 | + * Example 2: |
| 17 | + * Input: arr = [1,-2,-2,3] |
| 18 | + * Output: 3 |
| 19 | + * Explanation: We just choose [3] and it's the maximum sum. |
| 20 | + * |
| 21 | + * Example 3: |
| 22 | + * Input: arr = [-1,-1,-1,-1] |
| 23 | + * Output: -1 |
| 24 | + * Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0. |
| 25 | + * |
| 26 | + * Constraints: |
| 27 | + * 1 <= arr.length <= 10^5 |
| 28 | + * -10^4 <= arr[i] <= 10^4 |
| 29 | + * */ |
| 30 | +publicclass_1186 { |
| 31 | +publicstaticclassSolution1 { |
| 32 | +publicintmaximumSum(int[]arr) { |
| 33 | +//TODO: implement it |
| 34 | +return -1; |
| 35 | + } |
| 36 | + } |
| 37 | +} |