题目
给定一个整数数组，找出两个不重叠子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
给出数组[1, 3, -1, 2, -1, 2]，这两个子数组分别为[1, 3]和[2, -1, 2]或者[1, 3, -1, 2]和[2]，它们的最大和都是7
子数组最少包含一个数
要求时间复杂度为O(n)
解题
最大子数组I 这个题目是求一个数组中一个最大子数组的和，而本题目是求数组中的前两个最大子数组的和。然后就想到定义两个数组：left 、right 。
left[i] 表示从左开始到第i个值，并且包括第i个值的最大数组值
right[i]表示从size-1开始到第i个值，并且包括第i个值的最大数组
下面只需要找出两个数组和的最大值，并且两个数组的节点值不能有交集，这里需要遍历所有可能，时间复杂度是O(N2)
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) { // write your code int size = nums.size(); if(nums==null || size ==0) return 0; int[] left = new int[size]; int[] right = new int[size]; left[0] = nums.get(0); right[size-1] = nums.get(size-1); for(int i=1;i<size;i++){ left[i] = Math.max(left[i-1] + nums.get(i),nums.get(i)); } for(int j=size-2;j>=0 ;j--){ right[j] = Math.max(right[j+1] + nums.get(j),nums.get(j)); } int max = Integer.MIN_VALUE; for(int i=0;i<size;i++){ for(int j=size-1;j>i ; j--){ int tmp = left[i] + right[j]; max = Math.max(max,tmp); } } return max; } }
只求出左到右某个位置的最大子数组，再增加标志位来表示该位置是否是新的子数组的起始位置，然而后面不知道怎么搞了。
参考博客 上面定义的left数组 还是right数组中的值 是包含当前元素的最大值是 局部最大值
在上面博客中定义了全局最大值，这样定义的数组就是一个非降序的数组
数组left ，left[i] 表示从0 到i 这个区间内元素的最大值
同样可以求从i 到 size-1 这个区间的最大值
上面两个值之和的最大值就是答案了
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) { // write your code int size = nums.size(); if(nums==null || size ==0) return 0; int max = Integer.MIN_VALUE; int left[] = new int[size]; int localMax = 0; int globalMax = Integer.MIN_VALUE; for(int i=0;i< size;i++){ localMax = Math.max(localMax+nums.get(i) , nums.get(i)); globalMax = Math.max(localMax,globalMax); left[i] = globalMax; } localMax = 0; globalMax = Integer.MIN_VALUE; for(int i = size -1;i>=0;i--){ if(i< size -1) max = Math.max(max,globalMax+left[i]); localMax = Math.max(localMax + nums.get(i),nums.get(i)); globalMax = Math.max(localMax,globalMax); } return max; } }
上面的第二个for循环也就是求i 到size -1 区间内的全局最大值，然后就想到可以再定义一个数组
right right[i] 表示从i 到 size -1这个区间的最大
下面只需要根据这个两个数组求出最大值的和就好了
max = Math.max(left[i] + right[i+1],max)
再说明下：
left[i] 表示从0 到i 这个区间的最大值
right[i+1] 表示从 i + 1 都 size-1 这个区间的最大值
显然上面的和的最大值就是答案了
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) { // write your code int size = nums.size(); if(nums==null || size ==0) return 0; int max = Integer.MIN_VALUE; int left[] = new int[size]; int localMax = 0; int globalMax = Integer.MIN_VALUE; for(int i=0;i< size;i++){ localMax = Math.max(localMax+nums.get(i) , nums.get(i)); globalMax = Math.max(localMax,globalMax); left[i] = globalMax; } localMax = 0; globalMax = Integer.MIN_VALUE; int right[] = new int[size]; for(int i = size -1;i>=0;i--){ localMax = Math.max(localMax + nums.get(i),nums.get(i)); globalMax = Math.max(localMax,globalMax); right[i] = globalMax; } for(int i=0;i< size-1;i++){ max = Math.max(left[i] + right[i+1],max); } return max; } }
Python
class Solution: """ @param nums: A list of integers @return: An integer denotes the sum of max two non-overlapping subarrays """ def maxTwoSubArrays(self, nums): # write your code here if not nums: return 0 size = len(nums) left, right = [0 for i in range(size)], [0 for i in range(size)] MAX, localMax, globalMax = -sys.maxint - 1, 0, -sys.maxint-1 for i in range(size): localMax = max(localMax+ nums[i],nums[i]) globalMax = max(localMax,globalMax) left[i] = globalMax localMax = 0 globalMax = -sys.maxint - 1 for j in range(size-1,-1,-1): localMax = max(localMax + nums[j],nums[j]) globalMax = max(localMax,globalMax) right[j] = globalMax for i in range(size-1): MAX = max(left[i] + right[i+1],MAX) return MAX
这里为什么求了最小值，表示不理解
lintcode 中等题：maximum subarray最大子数组II
原文：http://www.cnblogs.com/theskulls/p/5106805.html
