Lintcode 45. Maximum Subarray Difference

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.

Example

Example 1:

Input:[1, 2, -3, 1]
Output:6
Explanation:
The subarray are [1,2] and [-3].So the answer is 6.

Example 2:

Input:[0,-1]
Output:1
Explanation:
The subarray are [0] and [-1].So the answer is 1.

Challenge

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

Notice

The subarray should contain at least one number

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

public class Solution {     /**      * @param nums: A list of integers      * @return: An integer indicate the value of maximum difference between two substrings      */     public int maxDiffSubArrays(int[] nums) {         // write your code here         if (nums == null || nums.length < 2) {             return 0;         }                   int n = nums.length;         int[] leftMax = new int[n];         int[] leftMin = new int[n];         int[] rightMax = new int[n];         int[] rightMin = new int[n];                   int curMax = Integer.MIN_VALUE;         int curMin = Integer.MAX_VALUE;         int minPreSum = 0;         int maxPreSum = 0;         int sum = 0;                   for (int i = 0; i < n; i++) {             sum += nums[i];             curMax = Math.max(curMax, sum - minPreSum);             curMin = Math.min(curMin, sum - maxPreSum);                           leftMax[i] = curMax;             leftMin[i] = curMin;                           minPreSum = Math.min(minPreSum, sum);             maxPreSum = Math.max(maxPreSum, sum);         }                   curMax = Integer.MIN_VALUE;         curMin = Integer.MAX_VALUE;         minPreSum = 0;         maxPreSum = 0;         sum = 0;                   for (int i = n - 1; i >= 0; i--) {             sum += nums[i];             curMax = Math.max(curMax, sum - minPreSum);             curMin = Math.min(curMin, sum - maxPreSum);                           rightMax[i] = curMax;             rightMin[i] = curMin;                           minPreSum = Math.min(minPreSum, sum);             maxPreSum = Math.max(maxPreSum, sum);         }                   int max = Integer.MIN_VALUE;         for (int i = 0; i < n - 1; i++) {             max = Math.max(max, Math.max(Math.abs(leftMax[i] - rightMin[i + 1]), Math.abs(rightMax[i + 1] - leftMin[i])));         }                   return max;               } }