[leetcode/lintcode 题解]阿里巴巴面试题：最大子数组 II

[hakunamatata11]

描述

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

在线评测地址：https://www.lintcode.com/problem/maximum-subarray-ii/?utm_source=sc-v2ex-fks

样例 1:

输入:
[1, 3, -1, 2, -1, 2]
输出:
7
解释:
最大的子数组为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2].

样例 2：

输入:
[5,4]
输出:
9
解释:
最大的子数组为 [5] 和 [4].

挑战

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

解题思路

这题是最大子段和的升级版。我们只要在求最大子段和的基础上，计算出前后缀的最大子段和，就可以枚举分界点来计算结果。

代码思路

对于前缀的最大子段和，我们可以先求以 i 位置为结尾的最大子段和的值 leftMax[i]。

max 中的两个参数分别代表延续前一个为结尾的最大字段和，或者当前的 nums[i]成为一段新的子段的两种情况。

计算前缀最大子段和 prefixMax，计算前缀最大值即可。

后缀的值也同理进行计算。

最后枚举分界点，取最大值，最终的结果为：

复杂度分析

设数组长度为 N 。

• 只需常数次地遍历数组，时间复杂度为 O(N)。

• 需要常数个额外数组来记录当前位置结尾前后缀最大连续和以及前后缀最大连续和，空间复杂度为 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 n = nums.size();

        // 计算以 i 位置为结尾的前后缀最大连续和
        List<Integer> leftMax = new ArrayList(nums);
        List<Integer> rightMax = new ArrayList(nums);

        for (int i = 1; i < n; i++) {
            leftMax.set(i, Math.max(nums.get(i), nums.get(i) + leftMax.get(i - 1)));
        }

        for (int i = n - 2; i >= 0; i--) {
            rightMax.set(i, Math.max(nums.get(i), nums.get(i) + rightMax.get(i + 1)));
        }

        // 计算前后缀部分的最大连续和
        List<Integer> prefixMax = new ArrayList(leftMax);
        List<Integer> postfixMax = new ArrayList(rightMax);

        for (int i = 1; i < n; i++) {
            prefixMax.set(i, Math.max(prefixMax.get(i), prefixMax.get(i - 1)));
        }

        for (int i = n - 2; i >= 0; i--) {
            postfixMax.set(i, Math.max(postfixMax.get(i), postfixMax.get(i + 1)));
        }

        int result = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            result = Math.max(result, prefixMax.get(i) + postfixMax.get(i + 1));
        }

        return result;
    }
}

更多题解参考：https://www.lintcode.com/problem/maximum-subarray-ii/?utm_source=sc-v2ex-fks