Maximum Subarray II

Med 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.

Thoughts

刚开始错误的想成找出两段和最大，相当于找出一段（夹在两段之间）和最小。实际上两段不一定要顶着头或尾，这样就不止一段和最小了。

我们把问题看成有一个外循环i把数组分成了左右两边。我们要找一个特定的i使得划分出来的左右两边内的子数组之和最大。 剩下的可以用preSum或者DP做。

Code

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 n = nums.size();

        // f: 以nums[i]为尾巴的最大值
        int[] f = new int[n];

        // init
        f[0] = nums.get(0);

        // loop
        for (int i = 1; i < n; i++) {
            f[i] = nums.get(i);
            if (f[i - 1] > 0) {
                f[i] += f[i - 1];
            }
        }

        // f: 前i的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (f[i] > max) {
                max = f[i]; 
            }
            f[i] = max;
        }

        // bf: 倒着的以nums[i]为尾巴的最大值
        // right part: 从n-1到i+1倒着看成一个数组，它的最大值
        int[] bf = new int[n];

        // init
        bf[n - 1] = nums.get(n - 1);

        // loop
        for (int i = n - 2; i >= 0; i--) {
            bf[i] = nums.get(i);
            if (bf[i + 1] > 0) {
                bf[i] += bf[i + 1];
            }
        }

        // bf: 后i的最大值
        max = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (bf[i] > max) {
                max = bf[i]; 
            }
            bf[i] = max;
        }

        max = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            // max sub array of left and right part
            max = Math.max(max, f[i] + bf[i + 1]); 
        }

        return max;
    }
}

Analysis

TC: O(n), SC: O(n)