最大子数组差
给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。...我们需要将数组划分为不重叠的两部分,求出左边最大子段和 leftMax,以及右边最小子段和 rightMin,然后相减求最大差值;或者求出左边最小子段和 leftMin 以及右边最大子段和 rightMax...举例:
nums = [2,-1,-2,1,-4,2,8]
从左到右,求左边的最大字段和 leftMax = [2, 1, -2, 1, -4, 2, 10]
从右向左,求右边的最小子段和 rightMin...,即可找到左边最大子段和以及右边最小子段和,然后相减求最大差值
同理,将原数组反转,按照相同的方法,从左到右,求出的是右边的最大子段和 rightMax = [8, 10, 6, 7, 5, 4, 6]...,然后相减求最大差值
返回 步骤 4 和 步骤 5 中求得的两个最大差值的最大值,就是所求答案。