整數數組中每對的距離和最大值的乘積和

Question

給定未排序的整數數組及其值。 需要計算每對之間距離的乘積和它們之間的最大值。

要更清楚。 比方說陣列A[] with 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)解決方案。