JAVA O(n) solution similar to maximum subarray sum
Similar to maximum subarray sum, we compute the maximum subarray sum including current element from left-to-right and right-to-left, and then compute min(global
Similar to maximum subarray sum, we compute the maximum subarray sum including current element from left-to-right and right-to-left, and then compute min(global subarray sum without deletion, left[i-1]+right[i+1]), which is the result.\n```\n public int maximumSum(int[] arr) {\n        int len = arr.length;\n        if (len == 0) {\n            return 0;\n        }\n        if (len == 1) {\n            return arr[0];\n        }\n        int result = Integer.MIN_VALUE;\n        int[] left = new int[len];\n        int[] right = new int[len];\n        left[0] = arr[0];\n        for (int i = 1; i < len; i++) {\n            left[i] = Math.max(arr[i], left[i-1]+arr[i]);\n            result = Math.max(result, left[i]);\n        }\n        right[len-1] = arr[len-1];\n        for (int i = len-2; i >= 0; i--) {\n            right[i] = Math.max(arr[i], right[i+1]+arr[i]);\n        }\n\n        for (int i = 1; i < len-1; i++) {\n            result = Math.max(left[i-1] + right[i+1], result);\n        }\n        return result;\n    }
[]