Machine Learning coder
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);
}
723 ·