题目链接: 45. 最大子数组差
给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。
给出数组 [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
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]|