Maximum Subarray Difference

Medium Maximum Subarray Difference

24%

Accepted

Given an array with integers.

Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.

Return the largest difference.

Have you met this question in a real interview? 

Yes

Example

For [1, 2, -3, 1], return 6

Note

The subarray should contain at least one number

Challenge

O(n) time and O(n) space.

public class Solution {

    /**

     * @param nums: A list of integers

     * @return: An integer indicate the value of maximum difference between two

     *          Subarrays

     */

    public int maxDiffSubArrays(ArrayList<Integer> nums) {

        // write your code

        int n = nums.size();

        int[] minLR = new int[n];

        int[] maxLR = new int[n];

        int[] minRL = new int[n];

        int[] maxRL = new int[n];

        minLR[0] = nums.get(0);

        maxLR[0] = nums.get(0);

        int pre = nums.get(0);

        for(int i = 1; i < n; i++){

            int sum = nums.get(i) + (pre > 0 ? 0 : pre);

            pre = sum;

            minLR[i] = Math.min(minLR[i-1], sum);

        }

        pre = nums.get(0);

        for(int i = 1; i < n; i++){

            int sum = nums.get(i) + (pre > 0 ? pre : 0);

            pre = sum;

            maxLR[i] = Math.max(maxLR[i-1], sum);

        }

        

        minRL[n-1] = nums.get(n-1);

        maxRL[n-1] = nums.get(n-1);

        pre = nums.get(n-1);

        for(int i = n-2; i >= 0; i--){

            int sum = nums.get(i) + (pre > 0 ? 0 : pre);

            pre = sum;

            minRL[i] = Math.min(minRL[i+1], sum);

        }

        pre = nums.get(n-1);

        for(int i = n-2; i >= 0; i--){

            int sum = nums.get(i) + (pre > 0 ? pre : 0);

            pre = sum;

            maxRL[i] = Math.max(maxRL[i+1], sum);

        }

        

        int maxDiff = 0;

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

            maxDiff = Math.max(maxDiff, Math.abs(maxRL[i+1] - minLR[i]));

            

        }

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

            maxDiff = Math.max(maxDiff, Math.abs(maxLR[i] - minRL[i+1]));

        }

        

        

        return maxDiff;

    }

}