Maximum Subarray II
Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.
Note The subarray should contain at least one number
Example For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, -2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.
解题思路
Maximum Subarray 中要求的是数组中最大子数组和，这里是求不相重叠的两个子数组和的和最大值，做过买卖股票系列的题的话这道题就非常容易了，既然我们已经求出了单一子数组的最大和，那么我们使用隔板法将数组一分为二，分别求这两段的最大子数组和，求相加后的最大值即为最终结果。隔板前半部分的最大子数组和很容易求得，但是后半部分难道需要将索引从0开始依次计算吗？NO!!! 我们可以采用从后往前的方式进行遍历，这样时间复杂度就大大降低了。
public int maxTwoSubArrays(ArrayList<Integer> nums) {
int len = nums.size();
int[] dp1 = new int[len];
int[] dp2 = new int[len];
// dp1[k] denotes the max sum to the left of k (inclusive)
// dp2[k] denotes the max sum to the right of k (inclusive)
dp1[0] = nums.get(0);
int newSum = nums.get(0);
for (int i = 1; i < len; i++) {
newSum = Math.max(newSum + nums.get(i),nums.get(i));
dp1[i] = Math.max(dp1[i - 1], newSum);
}
dp2[len - 1] = nums.get(len - 1);
newSum = nums.get(len - 1);
for (int i = len - 2; i >= 0; i--) {
newSum = Math.max(newSum+nums.get(i), nums.get(i));
dp2[i] = Math.max(dp2[i + 1], newSum);
}
// now for every node, calculate leftMaxSum + rightMaxSum
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < len - 1; i++) {
maxSum = Math.max(maxSum, dp1[i] + dp2[i + 1]);
}
return maxSum;
}
public int maxTwoSubArrays2(int[] nums) {
int len = nums.length;
int[] left = new int[len];
int[] right = new int[len];
int newSum = nums[0];
left[0] = nums[0];
for(int i=1;i < len;i++) {
newSum = Math.max(newSum+nums[i],nums[i]);
left[i] = Math.max(left[i-1],newSum);
}
right[len - 1] = nums[len-1];
newSum = nums[len-1];
for (int i=len-2; i>=0; i--) {
newSum = Math.max(newSum+nums[i], nums[i]);
right[i] = Math.max(right[i+1],newSum);
}
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < len - 1; i++) {
maxSum = Math.max(maxSum, left[i] + right[i + 1]);
}
return maxSum;
}