42-最大子数组 II

给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。

每个子数组的数字在数组中的位置应该是连续的。

返回最大的和。

注意事项

子数组最少包含一个数

样例

给出数组 [1, 3, -1, 2, -1, 2]

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

挑战

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

标签

贪心 枚举法 LintCode 版权所有 数组 子数组 前后遍历

思路

从左自右、从右自左分别遍历数组。每次遍历均记录当前最大的单子数组，用2个数组left,right保存。如left[i]的值表示nums从0至i中最大子数组的值，right[i]的值表示nums从i至size-1中最大子数组的值。

最后遍历left,right数组，left[i]+right[i+1]表示在第i位拆分数组，得到其子数组的和。

code

class Solution {

public:

    /**

     * @param nums: A list of integers

     * @return: An integer denotes the sum of max two non-overlapping subarrays

     */

    int maxTwoSubArrays(vector<int> nums) {

        // write your code here

        int size = nums.size(), i = 0, sum = 0, maxValue = 0;

        int *left = new int[size];

        sum = maxValue = left[0] = nums[0];

        for(i=1; i<size; i++) {

            if(sum < 0) {

                sum = nums[i];

            }

            else {

                sum += nums[i];

            }

            if(sum > maxValue) {

                maxValue = sum;

            }

            left[i] = maxValue;

        }

        int *right = new int[size];

        sum = maxValue = right[size-1] = nums[size-1];

        for(i=size-2; i>=0; i--) {

            if(sum < 0) {

                sum = nums[i];

            }

            else {

                sum += nums[i];

            }

            if(sum > maxValue) {

                maxValue = sum;

            }

            right[i] = maxValue;

        }

        int result = 0x80000000;

        for(i=0; i<size-1; i++) {

            result = (result > left[i]+right[i+1])?result:(left[i]+right[i+1]);

        }

        delete[] left;

        delete[] right;

        return result;

    }

};