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 限制，其中一个选项是尝试获得第一个。

因此，对于 (6,6,6) 和 K=2，算法应该是：找到 2 个最大元素（如果达到 K 个限制，取前 K 个）。在我们的例子中，它是第一个和第二个 6。然后分成子数组（从max到nextMax-1）

(6) + (6,6) => 6

一个很有趣的例子是 (6,7,6,6) 和 K=3 预期结果是

(6) + (7,6) + (6) = 19

我的算法不包括这种情况

伪代码：

1. indexes = FindKMaxIndexes() // Use selection algorithm https://en.wikipedia.org/wiki/Selection_algorithm, some variation to save indexes instead of elements values
2. reorder indexes from smallest to largest
3. i = 0
4. for each item in sorted indexes array
4.1 create subarray to include item (from i to current index)
4.2 i = current index + 1

Answer 2

其实问题好像是最大K数的和是多少。所以只需要按降序排序并对前K个数求和即可。

Answer 3

显然，我们可以得到 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] 反对。

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

Maximum value of sum of K partitioned subarrays

java

algorithm

partition