本文主要是介绍POJ1050 To the Max,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
To the Max
这个题目很经典的说,O(N^3)的DP。
首先偶们考察这样的题目,简化版:
已知一列数,求任意连续若干个数和的最大值。
SAMPLE: 3 2 -6 2 -1 7
原数3 2 -6 2 -1 7
处理3 5 -1 2 1 8
因为是连续若干个自然数的和,那么,前面的某个数字取与不取的条件在于:以前面这个数字为结尾的连续数的和最大值是否大于0,如果大于0,那么这个数字必然要会出现在包括数字的序列中,否则无法做到最大。
所以,显然。处理的原则是maxn[i]=max{0,maxn[i-1]}+a[i];
由于无须记录位置。所以,可以直接用一个变量sum代替maxn数组。O(n)的扫描即可。
单列数字的问题解决了,下面我们考察多列数字的
sample:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
我们可以将多列数字转换成单列数字来做! 可以这样设想,结果是一个长方形,我们把他压扁,使得宽为1。
引入辅助数组st,st[i][j]代表第i列从第1行开始的数字累加到第j行的值。那么,我们每次压扁的时候,就可以用st[i][j]-st[i][k -1]来表示第i列从第k个数字累加到第j个数字的值。达到压缩的效果。然后用上面单列数字的方法来做。算法时间复杂度O (N^3)
这篇关于POJ1050 To the Max的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!