方法一:正数扩大效应
因为正数具有扩大效应,所以要找连续子数组的最大和,我们就要从第二个数开始遍历数组
总结:从第二个数开始,如果前一个数是正数,就把这个数和自己相加,如果不是就不加,最后遍历一遍找最大值。
这样加了以后会有两种结果:要么还是正数,当然可能变大可能变小(特殊情况等会儿会讲)
要么是负数,说明当前自己这个数是个比较小的负数,那么抵消了前面的正数扩大效应,那么自己之后的那个数就不用加了。
当然,有些时候这个加正数的过程不总是有意义的。比如[7,-3,2]那么虽然7-3=4还是正数,但是加上2才为6,还没有7大。
但是没有关系,因为2还是变大了,也就是说我们把正数的扩大效应还是传下去了,只不过中间的负数比较大使得扩大效应比较小罢了,但是我们之后通过一此遍历找最大值也一定能够找到最大的那个数,而那个数,就是连续子数组的最大和。
这里还要提到全都不是正数的情况,这种情况就直接找一个最大值就行了,因为无论和那些数组成一组,都不会变大,要么变小,要么不变。