最大子段和

小trick:

    子段和:num=a[i]+a[i+1]+......a[j],num即为子段和

    现给出一段长度为n的数组,我们算子段和的最大值,我们先假设a[i]>=0,那么num=a[1]+a[2]+a[3]+......a[n],如果其中某些a[i]<0,num的最大值为多少?我们可以

先了解这样一个性质,设num=a[i]加到a[j],若果在i到j的期间有一个k,使得num<0,那么i到k所得到的num对后面的num的值只有消极影响(加上一个负数肯定变小嘛),

所以我们只需每次记录一下num的max值,在num小于0时将num清空,从k+1开始继续进行运算,直到求到j得出最大的num。

    ❀完结撒花❀

原文地址:https://www.cnblogs.com/fuhuayongyuandeshen/p/14186433.html