lintcode42- Maximum Subarray II- medium

Given an array of integers, find two non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

Notice

The subarray should contain at least one number

Example

For given

[1, 3, -1, 2, -1, 2]

, the two subarrays are

[1, 3]

and

[2, -1, 2]

[1, 3, -1, 2]

and

[2]

, they both have the largest sum

Challenge

Can you do it in time complexity O(n) ?

算法：分别算出left[]從左開始的最小subarray和right[]從右開始的最大subarray，然後開始求left[i] + right[i+1]的最大值。因為要求不重疊，是以你可以想象你在不斷挪動一個分割線，最後的結果就是找到那個分割線i，從最左開始到分割線左邊和從最右開始到分割線右邊這兩個分開的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(List<Integer> nums) {
        // write your code here
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        
        int[] sums = new int[nums.size() + 1];
        for (int i = 0; i < nums.size(); i++) {
            sums[i + 1] = sums[i] + nums.get(i);
        }
        
        int preMin = 0;
        int maxSum = Integer.MIN_VALUE;
        int[] left = new int[nums.size() + 1];
        for (int i = 1; i < sums.length; i++) {
            int crtSum = sums[i] - preMin;
            maxSum = Math.max(maxSum, crtSum);
            left[i] = maxSum;
            preMin = Math.min(preMin, sums[i]);
        }
        
        for (int i = 0; i < nums.size(); i++) {
            sums[i + 1] = sums[i] + nums.get(nums.size() - 1 - i);
        }
        preMin = 0;
        maxSum = Integer.MIN_VALUE;
        int[] right = new int[nums.size() + 1];
        for (int i = 1; i < sums.length; i++) {
            int crtSum = sums[i] - preMin;
            maxSum = Math.max(maxSum, crtSum);
            right[sums.length - i] = maxSum;
            preMin = Math.min(preMin, sums[i]);
        }
        
        int maxTotalSum = Integer.MIN_VALUE;
        for (int i = 1; i + 1 < right.length; i++) {
            maxTotalSum = Math.max(maxTotalSum, left[i] + right[i + 1]);
        }
        return maxTotalSum;
    }
}

轉載于:https://www.cnblogs.com/jasminemzy/p/7818874.html