K个分区子数组之和的最大值

Question

给定数组的一个子数组，它的值是它包含的出现奇数次的元素的最大值。我想将数组划分为 K 个子数组以最大化子数组值的总和。例如，如果我们有以下数组5 6 6 3 9 且 K=2我们可以将其划分如下：(5) + (6,6,3,9) = (5 + 9 => 14 )(5,6) + (6,3,9) = ( 6 +9 => 15 )(5,6,6) + (3,9) = ( 5 + 9 =>14 )(5,6,6,3) + (9) = ( 5 + 9 => 14 )我能够以粗暴的方式做到这一点，但正在寻找一种有效的算法。你能提出一些建议吗

Answer 1

实际上，问题似乎是最大 K 数的总和是多少。所以只需要按降序排序并对第一个 K 数求和即可。

Answer 2

显然，我们可以有O(n^2 * k)，因为如果f(i, k)代表可达到的最大可达A[i]用k零件，则：

f(i, k) = max(

  // include A[i] in previous part

  g(A[j..i]) + f(j - 1, k - 1),

  // don't include A[i] in previous part

  A[i] + f(i - 1, k - 1)

)

for all k <= j < i

where g(subarray) is the max element

in subarray that appears an odd number

of times

问题是我们如何更有效地选择要测试的子数组A[i]。