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] ，这是我们预先计算好的。