algorithm - 两个区间的最大和

Question

两个玩家 A 和 B 正在玩一个包含 N 个元素的数组 A 的游戏，其中每个玩家选择一个具有最大总和的数组间隔。另一个玩家同时选择同一数组中的另一个间隔，使得两个选择的间隔都遵循一定的规则:

1. 两个选定的间隔之间不应有任何内容。 IE。它们不应重叠。

2. 所选的两个间隔不应彼此太接近。第一个区间的结束点和第二个区间的开始点之间必须至少有 K 个索引距离。

3. 所选区间内的值之和应尽可能大。或者我们可以说两个选择的区间之和应该尽可能大。

我想要这两个间隔的总和。

示例:

令 N 等于 8，K 等于 3，A[] 等于 {6, 6, 0, -1, 4, 0, 3, -1}。最好选择 [1, 2] 和 [7, 7] 区间。这是我们能做出的唯一最优选择。

如果 12(来自第一个区间)+ 6(来自第二个区间)= 18，则总和

我知道寻找最大和连续子数组的 kadane 算法。但是在实现这个问题时遇到了麻烦。

Answer 1

另一位用户在事件编程竞赛中寻求问题的解决方案:

http://www.codechef.com/DEC13/problems/REIGN

你应该感到羞耻。