Maximum Subarray II

Description

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.

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]or[1, 3, -1, 2]and[2], they both have the largest sum7.

Challenge

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

Analysis

Maximum Subarray II 与 Maximum Subarray I 相比，有几处难点：

1. 两个不相邻subarray之和，原有的一个local变量不足，需要额外的变量来保存subarray sum，同时要求不相邻；定义left[], right[]两个数组分别保存从左到右和从右往左的subarray sum的结果

2. 子问题保存local最优解不够，还需要保存全局最优，因此left[]， right[]中存的其实是当前subarray sum的global最优；比如left[i] 就是[0, ..., i] 这个subarray的能取得的最大subarray sum，right[i]则表示[n - 1, ..., i] 能取得的最大subarray sum，这个最优解不一定包含i位置作为结尾。

3. 最后对left[]和right[]进行全局查询从而得到最终结果

用 local 变量更新然后返回 global 最优还不够，需要保存对于每一个子问题的 global 最优（可能并不以当前位置结尾），用于后面的左右两边全局查询

相比 Prefix Sum，个人更偏好Kadane's Algorithm，但是用 Kadane's Algorithm 要注意初始化问题（从头到尾循环，必须要以 nums[0] 做初始化，从 index = 1 开始搜；或者从尾到头循环则以nums[n-1]初始化，从index = n - 2开始）。

Solution

Kadane's Algorithm - O(n) space, O(n) time

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) {
        if (nums == null || nums.size() == 0) return 0;
        int n = nums.size();

        // left[] stores the global max subarray sum for [0, ..., i] 
        int[] left = new int[n];

        // right[] stores the global max subarray sum for [i, ..., n - 1] 
        int[] right = new int[n];

        // Initialize left[] array
        left[0] = nums.get(0);
        int prevMax = left[0];
        int max = left[0];
        // Loop from left to right
        for (int i = 1; i < n; i++) {
            prevMax = Math.max(prevMax + nums.get(i), nums.get(i));
            max = Math.max(max, prevMax);
            left[i] = max;
        }

        // Initialize right[] array
        right[n - 1] = nums.get(n - 1);
        prevMax = right[n - 1];
        max = right[n - 1];
        // Loop from right to left
        for (int i = n - 2; i >= 0; i--) {
            prevMax = Math.max(prevMax + nums.get(i), nums.get(i));
            max = Math.max(max, prevMax);
            right[i] = max;
        }

        // Find max sum of left and right subarrays
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            result = Math.max(result, left[i] + right[i + 1]);
        }

        return result;
    }
}

Prefix Sum Approach - O(n) space, O(n) time

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) {
        // write your code
        if(nums == null || nums.size() == 0) return 0;

        int n = nums.size();

        // Maximum subarray value from left/right with n elements
        int[] left = new int[n];
        int[] right = new int[n];

        int prefixSum = 0;
        int minSum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            prefixSum += nums.get(i);
            max = Math.max(max, prefixSum - minSum);
            minSum = Math.min(minSum, prefixSum);
            left[i] = max;
        }

        prefixSum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for(int i = n - 1; i >= 0; i--){
            prefixSum += nums.get(i);
            max = Math.max(max, prefixSum - minSum);
            minSum = Math.min(minSum, prefixSum);
            right[i] = max;
        }

        int rst = Integer.MIN_VALUE;

        for(int i = 0; i < n - 1; i++){
            rst = Math.max(rst, left[i] + right[i + 1]);
        }

        return rst;
    }
}

Reference

https://mnmunknown.gitbooks.io/algorithm-notes/626,_dong_tai_gui_hua_ff0c_subarray_lei.html