Given an unsorted Integer array with their values. Need to calculate sum of Multiplication of Distance between each pair and The value that is maximum between them.
To be more clear. Lets say array A[] with n elements
Calculate:-
for all i & j (i<j)
sum (distance(i,j)*(max(A[i],A[j])))
O(n^2) is easy. I want better than that. I've tried hard but don't know what data structure to use. I would request to give only a hint to solve this problem ( I will try from there )
This problem isn't very difficult.
My hint for you: for each i find all pairs if indexes in which the distance if multiplied by a[i]. This can be done effectively.
PS.
Can your give the link to this problem?
Someone asked me to solve this. Don't have link for this problem. The hint you gave is not clear. Can you elaborate a little.
For each i find all j > i such as a[i] >= a[j]. And you should add to the answer this value: a[i] * (j1 — i) + a[i] * (j2 — i) + ... + a[i] * (jk — i) = a[i] * (j1 — i + j2 — i + ... + jk — i). This sum can be found effectively (for example using Fenwick tree).