最大子数组差
给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。...Example:
给出数组 [1, 2, -3, 1], 返回 6 (|SUM([1,2]) - SUM([-3])|)
注意事项:子数组最少包含一个数
解题思路:
这题给人的第一感觉是可以用到最大子段和...我们需要将数组划分为不重叠的两部分,求出左边最大子段和 leftMax,以及右边最小子段和 rightMin,然后相减求最大差值;或者求出左边最小子段和 leftMin 以及右边最大子段和 rightMax...= [8, 2, -4, -3, -5, -6, -4] (之所以从右向左,是因为要保证两个子数组不重叠)
假设我们从 -2 的右边划分,则两个子数组为 [2,-1,-2] 和 [1,-4,2,8]...,即可找到左边最大子段和以及右边最小子段和,然后相减求最大差值
同理,将原数组反转,按照相同的方法,从左到右,求出的是右边的最大子段和 rightMax = [8, 10, 6, 7, 5, 4, 6]