题目链接： 45. 最大子数组差
给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。
Example:
给出数组 [1, 2, -3, 1], 返回 6 (|SUM([1,2]) - SUM([-3])|)
注意事项：子数组最少包含一个数
解题思路：
这题给人的第一感觉是可以用到最大子段和 Q53 Maximum Subarray。我们需要将数组划分为不重叠的两部分，求出左边最大子段和 leftMax，以及右边最小子段和 rightMin，然后相减求最大差值；或者求出左边最小子段和 leftMin 以及右边最大子段和 rightMax，然后相减求最大差值。
我们用4个 O(n) 的空间，利用最大字段和的动态规划的概念（最小子段和可以转化为最大字段和问题，只需要将列表中的元素全部取反，然后求最大字段和，再将结果取反即可。），分别存储 leftMax、rightMin、 leftMin、rightMax 这4个字段和，就可以在 O(n) 的时间内求出最大值。
举例：
nums = [2,-1,-2,1,-4,2,8]
- 从左到右，求左边的最大字段和 leftMax = [2, 1, -2, 1, -4, 2, 10]
- 从右向左，求右边的最小子段和 rightMin = [8, 2, -4, -3, -5, -6, -4] （之所以从右向左，是因为要保证两个子数组不重叠）
- 假设我们从 -2 的右边划分，则两个子数组为 [2,-1,-2] 和 [1,-4,2,8]，分别对应的 leftMax 和 rightMin 为 [2, 1, -2] 和 [8, 2, -4, -3]， leftMax 中应该是 2，rightMin 中应该是 -4，|2 - (-4)| = 6 。而 2 和 -4 对应的下标的关系为，将 rightMin 反转，-4 的下标比 leftMax 中 2 的下标多 1
- 因此，针对步骤 3 的方法，同时遍历求出的 leftMax 和 rightMin，即可找到左边最大子段和以及右边最小子段和，然后相减求最大差值
- 同理，将原数组反转，按照相同的方法，从左到右，求出的是右边的最大子段和 rightMax = [8, 10, 6, 7, 5, 4, 6] ；从右到左，求出的是左边的最小子段和 leftMin = [2, -1, -3, -2, -6, -4, 8]，按照步骤 3 的方法，同时遍历求出的 rightMax 和 leftMin，即可找到右边最大子段和以及左边最小子段和，然后相减求最大差值
- 返回 步骤 4 和 步骤 5 中求得的两个最大差值的最大值，就是所求答案。
Python 实现：
class Solution:
"""
@param nums: A list of integers
@return: An integer indicate the value of maximum difference between two substrs
"""
def maxDiffSubArrays(self, nums):
if len(nums) <= 1: # 子数组最少包含一个数
return 0
return max(self.dealDiff(nums), self.dealDiff(nums[::-1]))
# 最大子段和，返回子数组
def maxSubArrays(self, nums):
maxl = [nums[0]]
for i in range(1, len(nums)):
if maxl[i-1] < 0 or maxl[i-1] + nums[i] < 0:
maxl.append(nums[i])
else:
maxl.append(maxl[i-1] + nums[i])
return maxl
# 计算相减的结果，返回最大值
def dealDiff(self, nums):
retMax = float("-inf") # 返回值
leftMax = self.maxSubArrays(nums) # 从左到右，求最大子段和
inverseNums = [-num for num in nums]
# 最小子段和问题通过将各个元素取反可以转化为最大子段和问题
inverseRightMin = self.maxSubArrays(inverseNums[::-1]) # 从右到左，求最小子段和
rightMin = [-num for num in inverseRightMin][::-1]
for i in range(1, len(leftMax)):
retMax = max(retMax, abs(leftMax[i-1] - rightMin[i]))
# print(leftMax, rightMin, retMax)
return retMax
a = [2,-1,-2,1,-4,2,8]
print(Solution().maxDiffSubArrays(a)) # 16 # |[-1,-2,1,-4] - [2,8]|
