描述
给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。
子数组最少包含一个数
样例
给出数组[1, 2, -3, 1]，返回 6
挑战
时间复杂度为O(n)，空间复杂度为O(n)
思路：与上一题最大子数组II类似，只是要分情况找到sum(A)最大，sum(B)最小和sum(A)最小，sum(B)最大的情况
public int maxDiffSubArrays(int[] nums) {// write your code hereint[] leftMax = new int[nums.length];int[] leftMin = new int[nums.length];int[] rightMin = new int[nums.length];int[] rightMax = new int[nums.length];int curSum = 0;int maxSum = nums[0];int curDiff = 0;int minSum = nums[0];for (int i = 0; i < nums.length; i++) {curSum += nums[i];maxSum = Math.max(maxSum, curSum);curSum = Math.max(curSum, 0);leftMax[i] = maxSum;curDiff += nums[i];minSum = Math.min(minSum, curDiff);curDiff = Math.min(curDiff, 0);leftMin[i] = minSum;}curSum = 0;curDiff = 0;maxSum = nums[nums.length - 1];minSum = nums[nums.length - 1];for (int i = nums.length - 1; i >= 0; i--) {curDiff += nums[i];minSum = Math.min(minSum, curDiff);curDiff = Math.min(curDiff, 0);rightMin[i] = minSum;curSum += nums[i];maxSum = Math.max(maxSum, curSum);curSum = Math.max(curSum, 0);rightMax[i] = maxSum;}int result = 0;for (int i = 0; i < nums.length - 1; i++) {result = Math.max(result, Math.abs(leftMax[i] - rightMin[i + 1]));result = Math.max(result, Math.abs(leftMin[i] - rightMax[i + 1]));}return result;}