这并不是真正的作业,而是练习和优化,但这似乎是此类问题的最佳部分。
这是一个动态规划问题,如下:
-给定一个包含 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),但我没有想法,不知道如何开始。任何帮助表示赞赏!
最佳答案
一般来说,我们可以有一个简单的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)
。
关于java - 数组中 N 个元素的绝对差的最大和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58770400/