java - 数组中 N 个元素的绝对差的最大和

Question

这并不是真正的作业，而是练习和优化，但这似乎是此类问题的最佳部分。

这是一个动态规划问题，如下:

-给定一个包含 N 个元素的未排序数组，从中选取 K 个元素，使得它们的绝对差值最大。

此处计算相邻元素之间的绝对差。因此，如果我们有一个包含 5 个元素的数组:1 5 3 2 1，并且 k = 3，则绝对差异将为:

1 5 3 = |5-1| + |3-5| =6

1 5 2 = |5-1| + |2-5| =7

1 5 1 = [5-1| + |1-5| = 8

等等

其中 1 5 1 是最大的，需要 8

到目前为止，我尝试过通过递归找到 K 数字的所有可能组合，然后返回最大的(强力)来解决这个问题。

这表明这是一个糟糕的想法，因为例如当尝试使用 N=50 和 k=25 的数组时，有 1.264106064E+14 个组合。

我使用的递归是一个简单的递归，用于从数组中打印所有 K 位整数，只是不打印它们，而是将它们保存在数组中:

static void solve(int[] numbers, int k, int startPosition, int[] result) {
        if (k == 0) {
            System.out.println(absoluteDifferenceSum(result));
            return;
        }
        for (int i = startPosition; i <= numbers.length - k; i++) {
            result[result.length - k] = numbers[i];
            solve(numbers, k - 1, i + 1, result);
        }
    }

我想要实现的是最佳复杂度(我认为这里不能低于 O(n^2)，但我没有想法，不知道如何开始。任何帮助表示赞赏!

Answer 1

一般来说，我们可以有一个简单的O(n^2 * k)公式，其中f(i, k)代表选择的最佳结果k 个元素，当第 i 个元素位于所选内容的最右边时，

f(i, k) = max(
  f(j, k - 1) + abs(Ai - Aj)
)
for all j < i

我们可以扩展到

  max( f(j, k - 1) + Ai - Aj )
= Ai + max(f(j, k - 1) - Aj)

when Ai >= Aj

和

  max( f(j, k - 1) + Aj - Ai )
= -Ai + max(f(j, k - 1) + Aj)

when Ai < Aj

由于右被加数与Ai无关，我们可以构建一棵树，其节点存储f(j, k - 1) - Aj，以及f(j, k - 1) + Aj。此外，我们将在每个节点中存储每个子树的两个最大值。我们需要 O(k) 树。当我们到达最后一个元素时，让我们跳到检查树中的 k = 2:

1

5 -> 4 -> (-1, 9)

3 -> 2 -> (-1, 5)

2 -> 3 -> (-1, 5)

3 -> (-3, 5)

tree for k = 2 so far:

   3 (-1, 5)
  /         \
2 (-1, 5)   5 (-1, 9)

1 is less than 3 so we first add -1
to the max for the right subtree
stored for f(j, k - 1) + Aj

-1 + 9 = 8
(note that this represents {1,5,1})

then we continue left in the tree
and compare 8 to a similar calculation
with node 2: -1 + 5 = 4
(note that this represents {5,2,1})

这样，我们就可以将时间复杂度降低到 O(n log n * k)，并且空间 O(n * k)。