arrays - 整数数组中每对的距离与最大值的乘积之和

Question

给定一个未排序的整数数组及其值。 需要计算每对之间距离的乘积和它们之间的最大值。

更清楚。 假设数组 A[] 有 n 元素

计算:-

for all i & j (i<j)
sum (distance(i,j)*(max(A[i],A[j])))

O(n^2) 很简单。我想要比那更好的。 我已经很努力了，但不知道要使用什么数据结构。 我会要求只给出一个提示来解决这个问题(我会从那里尝试)

Answer 1

为简单起见，我假设所有数字都是不同的。

让我们从左到右迭代。我们来看看a[i]并将所有正确结束的部分添加到答案中。考虑所有 j < i .有两种可能的情况:

1. a[j] < a[i] .我们需要添加 a[i] * (i - j + 1)到答案。
2. a[j] > a[i] .我们需要添加 a[j] * (i - j + 1) .

让我们重写这两个和:第一个是 sum j < i and a[j] < a[i] of a[i] * (i - j + 1) = (a[i] * (i + 1) * number of such j) - (a[i] * (sum j < i and a[j] < a[i] of j)) .请注意 a[i] * (i + 1)和 a[i]独立于j ，所以它只是一个常数。我们只需要计算这样的数量 j那j < i and a[j] < a[i]和他们的总和有效。事实上，它是一个前缀的总和。平衡二叉搜索树可以处理这个问题，但我们不需要它。我们可以压缩坐标并改用二叉索引树。现在我们可以在 O(N log N) 中计算这个总和.

您可以对第二个总和做类似的事情以获得 O(N log N)解决方案。