arrays - 计算 k 个子数组的最大反转次数

Question

我有这个问题:

Given an array A and an integer K, partition A into K contiguous subarrays in the way that maximizes the sum of the number of inversions in each subarray. (An "inversion" is a pair of indices i, j where i < j and A[i] > A[j].)

Return the sum.

For example, if A = 9 1 7 2 3 and K = 2, then the answer is 4, because you can split the array into 9 1 7 2 (which has four inversions) and 3 (which has none), and 4 + 0 = 4.

Constaints

1 <= A.size <= 500
1 <= k <= A.size
1 <= A[i] <= 100000

我的想法:

• 这看起来像是一个动态编程问题，但我不知道如何集成 K分组到解决方案中。

• 这个问题大致可以翻译为查找 K组，每个组在该组内具有最多数量的递增元素。

任何有关如何解决此问题的想法都会有所帮助。

Answer 1

我们至少可以有一个O(n^2 * k)动态程序。让f(i, k)代表最多索引 i 的反转与 k组。然后:

f(i, k) = max(
  inversion_count(j, i) + f(j - 1, k - 1)
)
for k <= j <= i

我们可以预先计算一个步骤来得出 inversion_count(interval) 的结果O(1)使用 O(n^2) 的时间时间和空间:对于所有元素，e ，在 A ，存储从e开始的每个区间中有多少个较小的元素。当我们减少j在主迭代中，增加间隔的大小，反转次数会增加小于 A[j] 的元素数量。在区间 [j, i] ，我们已经预先计算好了。