package leetcode;

/**
 * https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/
 */
public class Problem1186 {
    public int maximumSum(int[] arr) {
        int answer = arr[0];
        int maxSoFar = arr[0];
        int[] forward = new int[arr.length];
        forward[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxSoFar = Math.max(arr[i], maxSoFar + arr[i]);
            forward[i] = maxSoFar;
            answer = Math.max(answer, maxSoFar);
        }
        maxSoFar = arr[arr.length - 1];
        int[] backward = new int[arr.length];
        backward[backward.length - 1] = arr[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            maxSoFar = Math.max(arr[i], maxSoFar + arr[i]);
            backward[i] = maxSoFar;
            answer = Math.max(answer, maxSoFar);
        }
//        System.out.println(Arrays.toString(forward));
//        System.out.println(Arrays.toString(backward));
        for (int i = 1; i < arr.length - 1; i++) {
            answer = Math.max(answer, forward[i - 1] + backward[i + 1]);
        }
        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
        System.out.println(prob.maximumSum(new int[]{-2, -3, 4, -1, -2, 1, 5, -3})); // 9
    }
}

@@ -852,121 +852,8 @@
   %7D%0A
-//        System.out.println(Arrays.toString(forward));%0A//        System.out.println(Arrays.toString(backward));%0A
     
@@ -1014,655 +1014,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1186 prob = new Problem1186();%0A        System.out.println(prob.maximumSum(new int%5B%5D%7B1, -2, 0, 3%7D)); // 4%0A        System.out.println(prob.maximumSum(new int%5B%5D%7B1, -2, -2, 3%7D)); // 3%0A        System.out.println(prob.maximumSum(new int%5B%5D%7B-1, -1, -1, -1%7D)); // -1%0A        System.out.println(prob.maximumSum(new int%5B%5D%7B1, -2, -1, 0, 3%7D)); // 3%0A        System.out.println(prob.maximumSum(new int%5B%5D%7B1, 2, 3%7D)); // 6%0A        System.out.println(prob.maximumSum(new int%5B%5D%7B-4, 1, 2, -3, 3, -4, 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

Solve problem 1186