题目
最大子数组 II
给定一个整数数组，找出两个不重叠子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
给出数组[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;
}
}
Java Code
只求出左到右某个位置的最大子数组，再增加标志位来表示该位置是否是新的子数组的起始位置，然而后面不知道怎么搞了。
参考博客 上面定义的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;
}
}
Java Code
上面的第二个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;
}
}
Java Code
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
Python Code
这里为什么求了最小值，表示不理解