I think I have a solution. The idea is to determine the contribution of each element to the final answer.
Note that we can get the range [l, r] for which a given element holds the maximum value using a stack in O(n) time (the idea is based on this). Now, the task which remains is to get the lengths of the subarrays.
Let’s denote the current element’s position in the array by pos and its value by val.
We have to determine the lengths of the subarrays [i, j] in the range [l, r] such that l <= i, j <= r and i <= pos <= j. Let’s denote x as the length [l, pos] and y as the length [pos, r].
Then, we can say that we need the sum of the lengths of the subarrays [pos, pos], [pos, pos+1], ..., [pos, r], [pos -1, pos], [pos -1, pos + 1], ..., [pos - 1, r], [pos - 2, pos], ..., [l, r].
Observe the pattern here… This sum can be expressed as (\sum_{i=1}^{x}i ) \times y + (\sum_{i=1}^{y-1}i ) \times x.
So, the contribution for the current element becomes val \times ((\sum_{i=1}^{x}i ) \times y + (\sum_{i=1}^{y-1}i ) \times x). Note that this value can be calculated in O(1). The final answer can be calculated by simply summing the contribution of each element. So, the final complexity is O(n).
Example:
arr = [1, 2, 3]
for 1 → x = 1 and y = 1 so its contribution = 1 \times ((\sum_{i=1}^{1}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 1) = 1
for 2 → x = 2 and y = 1 so its contribution = 2 \times ((\sum_{i=1}^{2}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 2) = 6
for 3 → x = 3 and y = 1 so its contribution = 3 \times ((\sum_{i=1}^{3}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 3) = 18
So, the final answer = 1 + 6 + 18 = 25
Code
