1

给定 N 个数字（正数和负数）并且 T = 您可以选择的数字数，您如何计算区间的最大总和？区间的第一个数字被认为是 0。

例如： N=5 T=4 and {3 9 1 1 7} 最大和是 16 来自 (3, 9) 和 (1, 7) ！记住 3 和 1 被认为是 0，因为它们是它们间隔中的第一个数字。我想出了一个解决方案，但是当我添加负数时它会搞砸。N=4 T=3 和 {-2 1 -3 -4} 解是 1 (-2, 1) 和 (-3 -3) （当你使用负数时，你可以考虑由相同的负数形成的区间数字 (-3 -3) = 0)。有任何想法吗？

*稍后编辑：我的代码有什么问题？http://pastebin.com/QTTTrvUz

4

1 回答 1

1

动态编程是你的朋友：

假设我们可以选择数字，让我们S[i][j]表示仅考虑第一个数字时可以获得的最大总和。ij

然后：

  1. S[i][j] = S[i - 1][j], 如果i不在一个段中。
  2. S[i][j] = S[i - k][j - k] + value_of_segment(i - k + 1, i)，如果i在一段长度中k。

我们让S[i][j] = max((1), (2)).

value_of_segment可以预先计算在O(n).

S[i][j]可以计算在O(N * T^2).

于 2013-03-20T22:14:56.780 回答