Maximum Subarray Sum with One Deletion LeetCode solution in Java

1
class Solution {
2
  public int maximumSum(int[] arr) {
3
    int n = arr.length;
4
    int[] prefixSum = new int[n + 1];
5
    prefixSum[0] = 0;
6
    int ans = (int) -1e9;
7
    for (int i = 1; i <= n; i++) {
8
      prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
9
      ans = Math.max(ans, arr[i - 1]);
10
    }
11
    if (ans < 0) return ans;
12
    for (int i = 1; i <= n; i++) {
13
      if (arr[i - 1] < 0) {
14
        int leftPrefixSum = 0;
15
        // find max in i to 0
16
        for (int j = i - 1; j >= 0; j--) {
17
          leftPrefixSum = Math.max(leftPrefixSum, prefixSum[i - 1] - prefixSum[j]);
18
        }
19

20
        int rightPrefixSum = 0;
21
        // find max in i to n
22
        for (int j = i + 1; j <= n; j++) {
23
          rightPrefixSum = Math.max(rightPrefixSum, prefixSum[j] - prefixSum[i]);
24
        }
25
        ans = Math.max(ans, leftPrefixSum + rightPrefixSum);
26
      }
27
    }
28
    return Math.max(ans, prefixSum[n]);
29
  }
30
}