LintCode第42题-最大子数组 II
描述
给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和
子数组最少包含一个数
样例 1：
输入：
nums = [1, 3, -1, 2, -1, 2]输出：
7解释：
最大的子数组为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2].
样例 2：
输入：
nums = [5,4]输出：
9解释：
最大的子数组为 [5] 和 [4].
挑战
要求时间复杂度为 O(n)
思路:
主要分为两种解题方法
第一种:动态累加和 + 最大子数组和
第二种:前缀和快速计算 左侧最大子数组和 和 右侧最大子数组和，从而找到两个不重叠子数组的最大和
但前缀和有一个点 可以快速计算区间和
下面是第一种解法:
代码如下:
public class Solution {
/**
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
public int maxTwoSubArrays(List<Integer> nums) {
int[] numArray = nums.stream().mapToInt(Integer::intValue).toArray();
int n = numArray.length;
// 左侧最大子数组和
int[] leftMax = new int[n];
int currentSum = 0, maxSum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
currentSum = (currentSum > 0 ? currentSum : 0) + numArray[i];//如果是负值将其变为0
maxSum = Math.max(maxSum, currentSum);
leftMax[i] = maxSum;
}
// 右侧最大子数组和
int[] rightMax = new int[n];
currentSum = 0;
maxSum = Integer.MIN_VALUE;
for (int i = n - 1; i >= 0; i--) {
currentSum = (currentSum > 0 ? currentSum : 0) + numArray[i];
maxSum = Math.max(maxSum, currentSum);
rightMax[i] = maxSum;
}
// 计算最大不重叠子数组和
int finalResultSum = Integer.MIN_VALUE;
//依次遍历两个左子数组和右子数组 得到其组合的最大值即为最大的返回值
for (int i = 0; i < n - 1; i++) {
finalResultSum = Math.max(finalResultSum, leftMax[i] + rightMax[i + 1]);
}
return finalResultSum;
}
}