MaxDoubleSliceSum

/*
Find the maximal sum of any double slice. 
*/
class Solution {
    public int solution(int[] A) {
        int maxSum = Integer.MIN_VALUE;
        int N = A.length;
        
        if (N == 3) return 0;
        
        // rightSum[i] is A[Y+1] + .... + A[Z-1] when Y = i
        int[] rightSum = new int[A.length];
        rightSum[N - 1] = 0; // Y cannot be N-1
        rightSum[N - 2] = 0; 
        for (int i = A.length-3; i >= 1; i--) {
            rightSum[i] =  Math.max(A[i + 1] + rightSum[i + 1], 0);
        }
        
        // left[i] is A[X+1] + .... + A[Y-1] when Y = i
        int[] leftSum = new int[A.length];
        leftSum[0] = 0; // Y cannot be N-1
        
        for (int i = 1; i < A.length-1; i++) {
            if(i == 1) leftSum[i] = 0;
            else leftSum[i] = Math.max(A[i - 1] + leftSum[i - 1], 0);
            
            //System.out.println(i + " " + leftSum[i] + " " + rightSum[i]);
            maxSum = Math.max(maxSum, leftSum[i] + rightSum[i]);
        }
        
        
        return maxSum;
    }
}