HDU 1024 Max Sum Plus Plus

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1024

题目翻译

将一个长度为 N 的序列,分为 M 段,使得 M 段之和最大。

题解

这道题目没有说M的范围,于是我思索了好久。然而并不会做M很大的。
于是我们用F[i][j]表示当前分为 i 段,以 j 为结尾的最大和,然后F[i][j] = max(F[i][j-1] + num[j] , F[i-1][1~j] + num[j])
当然,这是可以优化到一维的,同理。

代码