连续子数组的和的绝对值的最大值、最小值(非绝对值的话直接dp动态规划)

前缀和的思路:

sum[i] = num[0]+num[1]+......+num[i-1]

sum[j] = num[0]+num[1]+......+num[j-1]

那么:num[i]+num[i+1]+....num[j] = sum[j+1] - sum[i]

所以求连续子数组绝对值的最大最小,即可转化为求前缀和排序的差值的绝对值。

例如: -2 1 -3 4 -1 2 1   sum数组:-2  -1  -4  0   -1   1   2  》  -4 -2 -1  -1  0  1  2 

1、最小值:可能是0,如果前缀和中有0值,那么直接返回0;否则,前缀和绝对值最小值可能有两种情况.

@1: sum前缀和数组排序后相邻的差值绝对值最小的。

@2:  或者sum[i]最小。

2、最大值:前缀和绝对值最大有两种情况

@1: sum前缀和数组排序后sum[i]-sum[0]绝对值最大。

@2: sum[i]绝对值最大。 

原文地址:https://www.cnblogs.com/wsw-seu/p/13700006.html