Max Sum Plus Plus

【原题链接】

【题意说明】

有n个数的序列,求连续m段数的和最大!

【问题分析】

dp问题!令f[i][j]表示j个数(第j个数必选),分成连续i段的最大和,显然有:

f[i][j]=max(f[i][j-1], f[i-1][k])+a[j] {j的取值范围为i~n,k的取值范围为i~j-1} 

这里要注意的是对于每个f[i][j]都要扫描一遍k的话,肯定会超时!由于对不同j,k都是从i开始扫描,所以可以用一个变量记录前f[i-1][k]的最大值,这样就减少一重循环!

最后数值比较大,要用int64型!

原文地址:https://www.cnblogs.com/ahmasoi/p/2781139.html