package leetcode;

/**
 * https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/
 */
public class Problem1186 {
    public int maximumSum(int[] arr) {
        int answer = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            boolean negative = false;
            int sum = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < 0) {
                    if (negative) {
                        break;
                    }
                    negative = true;
                } else {
                    sum += arr[j];
                }
            }
            answer = Math.max(answer, sum);
        }
        return answer;
    }

    public static void main(String[] args) {
        Problem1186 prob = new Problem1186();
        System.out.println(prob.maximumSum(new int[]{1, -2, 0, 3})); // 4
        System.out.println(prob.maximumSum(new int[]{1, -2, -2, 3})); // 3
        System.out.println(prob.maximumSum(new int[]{-1, -1, -1, -1})); // -1
        System.out.println(prob.maximumSum(new int[]{1, -2, -1, 0, 3})); // 3
        System.out.println(prob.maximumSum(new int[]{1, 2, 3})); // 6
        System.out.println(prob.maximumSum(new int[]{-4, 1, 2, -3, 3, -4, 2})); // 6
    }
}

@@ -184,139 +184,118 @@
 r = 
-Integer.MIN_VALUE;%0A        for (int i = 0; i %3C arr.length; i++) %7B%0A            boolean negative = false;%0A            int sum
+arr%5B0%5D;%0A        int maxSoFar = arr%5B0%5D;%0A        int%5B%5D forward = new int%5Barr.length%5D;%0A        forward%5B0%5D
  = arr%5B
-i
+0
 %5D;%0A 
@@ -305,20 +305,16 @@
     
-    
 for (int
  j =
@@ -313,21 +313,17 @@
 (int
- j =
  i 
-+
+=
  1; 
-j
+i
  %3C a
@@ -333,17 +333,17 @@
 length; 
-j
+i
 ++) %7B%0A  
@@ -356,65 +356,139 @@
     
-    if (arr%5Bj%5D %3C 0) %7B%0A                    if (negative) %7B
+maxSoFar = Math.max(arr%5Bi%5D, maxSoFar + arr%5Bi%5D);%0A            forward%5Bi%5D = maxSoFar;%0A            answer = Math.max(answer, maxSoFar);
 %0A   
@@ -488,32 +488,34 @@
 r);%0A        
+%7D%0A
         
         brea
@@ -506,106 +506,343 @@
     
-        break;%0A                    %7D%0A                    negative = true;%0A                %7D else %7B
+maxSoFar = arr%5Barr.length - 1%5D;%0A        int%5B%5D backward = new int%5Barr.length%5D;%0A        backward%5Bbackward.length - 1%5D = arr%5Barr.length - 1%5D;%0A        for (int i = arr.length - 2; i %3E= 0; i--) %7B%0A            maxSoFar = Math.max(arr%5Bi%5D, maxSoFar + arr%5Bi%5D);%0A            backward%5Bi%5D = maxSoFar;%0A            answer = Math.max(answer, maxSoFar);
 %0A   
@@ -842,32 +842,36 @@
 r);%0A        
+%7D%0A//
         
     sum += a
@@ -862,58 +862,161 @@
     
-    sum += arr%5Bj%5D;%0A                %7D%0A            %7D
+System.out.println(Arrays.toString(forward));%0A//        System.out.println(Arrays.toString(backward));%0A        for (int i = 1; i %3C arr.length - 1; i++) %7B
 %0A   
@@ -1050,19 +1050,48 @@
 answer, 
-sum
+forward%5Bi - 1%5D + backward%5Bi + 1%5D
 );%0A     
@@ -1587,24 +1587,24 @@
  3%7D)); // 6%0A
-
         Syst
@@ -1672,20 +1672,110 @@
  2%7D)); // 6%0A
+        System.out.println(prob.maximumSum(new int%5B%5D%7B-2, -3, 4, -1, -2, 1, 5, -3%7D)); // 9%0A
     %7D%0A%7D%0A

Update problem 1186