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):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; } }
No comments:
Post a Comment