public class Solution {
/**
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
public int maxTwoSubArrays(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int[] left = new int[nums.size()];
int[] right = new int[nums.size()];
// left to right
int max = Integer.MIN_VALUE;
int sum = 0, minSum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums.get(i);
max = Math.max(max, sum - minSum);
minSum = Math.min(minSum, sum);
left[i] = max;
}
// right to left
max = Integer.MIN_VALUE;
sum = 0;
minSum = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
sum += nums.get(i);
max = Math.max(max, sum - minSum);
minSum = Math.min(minSum, sum);
right[i] = max;
}
// update for max
max = Integer.MIN_VALUE;
for (int i = 0; i < nums.size() - 1; i++) {
max = Math.max(max, left[i] + right[i + 1]);
}
return max;
}
}