freshman MaxSum
记录j
之前的最大子段和,ThisSum
记录的是从前面所有子段和都是负数的下标开始到j
的所记录的子段和,如果ThisSum
记录的子段和小于0,那么就可以重置为0,如5 -3 2 -7 6 1 8
,运行到-7
时ThisSum == -3
,那么我们不选取前面的数字的话,结果会更优,这时更新ThisSum
为0。
(也许讲的不怎么好,但是动动手写一写还是能明白的,
当然还有一种解法:就是用前缀和,由于一个从n到m子段和能用前m个数的和减去前n-1个数的和得到,那么我们只需要记录并维护j
之前出现过的最小前缀和,取当前的前缀和与最小前缀和之差的最大值,就是一个最大的子段和