lintcode:最大子数组II

题目

最大子数组 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

这里为什么求了最小值,表示不理解

上一篇:lintcode 最大子数组III


下一篇:lintcode:最大子数组差