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.
The subarray should contain at least one number
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.
Can you do it in time complexity O(n) ?
Analysis:
We need two non-overlapping subarrays, so there must be some point X so that the maximum subarray before X (not necessarily end at X) + the maximum subarray after X is max.
So, we first calculate the max subarray end at each point from left to right and from right to left;
Then, we account the max subarray before and after each point;
At last, we find out the result.
Solution:
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @return: An integer denotes the sum of max two non-overlapping subarrays 5 */ 6 public int maxTwoSubArrays(ArrayList<Integer> nums) { 7 if (nums.size()<2) return 0; 8 int len = nums.size(); 9 10 //Calculate the max subarray from left to right and from right to left. 11 int[] left = new int[len]; 12 left[0] = nums.get(0); 13 for (int i=1;i<len;i++) 14 left[i] = Math.max(left[i-1]+nums.get(i), nums.get(i)); 15 int curMax = left[0]; 16 for (int i=1;i<len;i++) 17 if (left[i]<curMax){ 18 left[i] = curMax; 19 } else curMax = left[i]; 20 21 int[] right = new int[len]; 22 right[len-1]=nums.get(len-1); 23 for (int i=len-2;i>=0;i--) 24 right[i] = Math.max(right[i+1]+nums.get(i),nums.get(i)); 25 curMax = right[len-1]; 26 for (int i=len-2;i>=0;i--) 27 if (right[i]<curMax) right[i] = curMax; 28 else curMax = right[i]; 29 30 //Find out the result. 31 int res = Integer.MIN_VALUE; 32 for (int i=0;i<len-1;i++) 33 if (left[i]+right[i+1]>res) 34 res = left[i]+right[i+1]; 35 return res; 36 } 37 }
原文：http://www.cnblogs.com/lishiblog/p/4183818.html