哪位高手能给小弟我说说DP解决最长子段和有关问题，网下说的版本好多，看不懂

谁能给我说说DP解决最长子段和问题，网上说的版本好多，看不懂！
RT
[解决办法]

引用:

引用:最大子段和？
设a为原数组，f[i]表示以a[i]结尾且包含a[i]的最大子段和，那么如果f[i-1]>0，那么f[i]就可以要前面的子段(f[i]=f[i-1]+a[i])，否则f[i]=a[i]，因为总是可以放弃那些取值为负的子段
然后扫一遍f取最大的就是最大子段和

前面的子段是小于零的比如是a[m]~a[n],怎么就能保证m~n的子……

嗯。。。
这里求的是“以a[i]结尾（包含a[i]）的最大子段和”，然后扫一遍f取最大值。因为最大子段和总是要以a中的一个元素结尾的，所以最大子段和肯定在f中。
举个例子，a[] = {1,2,-5,1}
那么f[] = {1,3,-2,1}
扫一边f，取最大值为max(f[i]) = f[1] = 3，也就是说最大子段是以a[1]结尾且包含a[1]的一个子串
可以认为你想说的m=0,n=2,而最大子段和是a[0]+a[1]=f[1]=3，即包含在a[m]~a[n]中，有什么问题么？

求f[3]时由于f[2]是负的，干脆就不要前面的结果了，所以f[3]=a[3]=1。毕竟最大子段和要求子段是连续的，否则你取a中所有的正数加起来就完事了，所以a[0]~a[2]中是否有全局的最大子段和，跟求f[3]毛关系都没有。

查看更多 下一篇