最大子数组差

题目链接： 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]

1. 从左到右，求左边的最大字段和 leftMax = [2, 1, -2, 1, -4, 2, 10]
2. 从右向左，求右边的最小子段和 rightMin = [8, 2, -4, -3, -5, -6, -4] （之所以从右向左，是因为要保证两个子数组不重叠）
3. 假设我们从 -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
4. 因此，针对步骤 3 的方法，同时遍历求出的 leftMax 和 rightMin，即可找到左边最大子段和以及右边最小子段和，然后相减求最大差值
5. 同理，将原数组反转，按照相同的方法，从左到右，求出的是右边的最大子段和 rightMax = [8, 10, 6, 7, 5, 4, 6] ；从右到左，求出的是左边的最小子段和 leftMin = [2, -1, -3, -2, -6, -4, 8]，按照步骤 3 的方法，同时遍历求出的 rightMax 和 leftMin，即可找到右边最大子段和以及左边最小子段和，然后相减求最大差值
6. 返回 步骤 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]|