42. 最大子数组 II

描述

给定一个整数数组，找出两个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的和。

注意事项

子数组最少包含一个数

样例

给出数组
[1, 3, -1, 2, -1, 2]这两个子数组分别为
[1, 3]和[2, -1, 2]或者[1, 3, -1, 2]和[2]，它们的最大和都是
7

挑战
要求时间复杂度为 O(n)

思路

这个题的思路是，因为两个subarray 一定不重叠，所以必定存在一条分割线，分开这两个 subarrays，所以最后的部分里：

  max = Integer.MIN_VALUE;
        for(int i = 0; i < size - 1; i++){
            max = Math.max(max, left[i] + right[i + 1]);
        }
        return max;

这里是在枚举这条分割线的位置，然后 left[] 和 right[] 里分别存的是，某个位置往左的 maximum subarray 和往右的 maximum subarray

代码

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) {
        int size = nums.size();
        int[] left = new int[size];
        int[] right = new int[size];
        
        // 当前i往左的最大子数组和
        int sum = 0;
        int minSum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < size; i++) {
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(sum, minSum);
            left[i] = max;
        }
        
        // 当前i往右的最大子数组和
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for (int i = size - 1; i >= 0; i--) {
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(sum, minSum);
            right[i] = max;
        }
        
        max = Integer.MIN_VALUE;
        // left[i]和right[i + 1]之间存在分割线
        // right是i + 1，i 最大取size - 2，不能越界
        for (int i = 0; i < size - 1; i++) {
            max = Math.max(max, left[i] + right[i + 1]);
        }
        return max;
    }
}

总结

关于前缀序列求和，值得注意的是，比如当前 i 的max是5，若i + 1的sum小于max则i + 1的max仍为5，即对于left数组，left[i] = 5，
left[i + 1] = 5

42. 最大子数组 II

代码

推荐阅读更多精彩内容