首页 > 其他 > 详细

LintCode-Maximum Subarray II

时间:2014-12-25 08:42:28      阅读:914      评论:0      收藏:0      [点我收藏+]

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.

Challenge

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

原文:http://www.cnblogs.com/lishiblog/p/4183818.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!