最大子数组差

给出数组 [1, 2, -3, 1], 返回 6 (|SUM([1,2]) - SUM([-3])|)

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]|