数组中 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) 表示当第 i 个元素在最右边时选择 k 个元素的最佳结果选择，

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) 和 space O(n * k)。

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

Largest sum from absolute differences of N elements in an array

java

arrays

algorithm

dynamic-programming

absolute-value