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(&nbsp; // include A[i] in previous part&nbsp; g(A[j..i]) + f(j - 1, k - 1),&nbsp; // don't include A[i] in previous part&nbsp; A[i] + f(i - 1, k - 1))for all k <= j < iwhere g(subarray) is the max elementin subarray that appears an odd numberof times问题是我们如何更有效地选择要测试的子数组A[i]。