最大子数组差
给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。...Example:
给出数组 [1, 2, -3, 1], 返回 6 (|SUM([1,2]) - SUM([-3])|)
注意事项:子数组最少包含一个数
解题思路:
这题给人的第一感觉是可以用到最大子段和...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, -...-6, -4, 8],按照步骤 3 的方法,同时遍历求出的 rightMax 和 leftMin,即可找到右边最大子段和以及左边最小子段和,然后相减求最大差值
返回 步骤 4 和 步骤 5 中求得的两个最大差值的最大值