首页 > 代码库 > LintCode-Maximum Subarray II
LintCode-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.
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 }
LintCode-Maximum Subarray II