Publicationpublic int solve(int[] A) {

public int solve(int[] A) {     int n = A.length;     int mod = 1000000007;     // calculate prefix sum and suffix sum arrays     long[] prefixSum = new long[n];     long[] suffixSum = new long[n];     prefixSum[0] = A[0];     suffixSum[n-1] = A[n-1];     for (int i = 1; i < n; i++) {         prefixSum[i] = prefixSum[i-1] + A[i];         suffixSum[n-1-i] = suffixSum[n-i] + A[n-1-i];     }     // calculate the maximum sum of one subarray from the left     long[] maxSumLeft = new long[n];     long curSum = 0;     long curMax = Long.MIN_VALUE;     for (int i = 0; i < n; i++) {         curSum += A[i];         curMax = Math.max(curMax, curSum);         maxSumLeft[i] = curMax;         curSum = Math.max(curSum, 0);     }     // calculate the maximum sum of one subarray from the right     long[] maxSumRight = new long[n];     curSum = 0;     curMax = Long.MIN_VALUE;     for (int i = n-1; i >= 0; i--) {         curSum += A[i];         curMax = Math.max(curMax, curSum);         maxSumRight[i] = curMax;         curSum = Math.max(curSum, 0);     }     // calculate the maximum sum of three subarrays     long maxSum = Long.MIN_VALUE;     for (int i = 1; i < n-1; i++) {         long sum1 = maxSumLeft[i-1];         long sum2 = maxSumRight[i+1];         long sum3 = prefixSum[i-1] + suffixSum[i+1];         maxSum = Math.max(maxSum, sum1+sum2+sum3);     }     return (int)(maxSum % mod); }