Problem Explanation
You are given an array of length N. You have to output the sum of difference between maximum and minimum elements for all sub-arrays.
Approach
This problem can be broken down into two parts. We can first find the sum of the maximum elements of all the subarrays and the sum of the minimum elements of all the subarrays and find their difference. To find the minimum elements of all the subarrays we calculate two arrays - prefix array and suffix array. In prefix array we store the index of the element to the left, which is smaller than the element at the current index. And in suffix array we store the index of the element to the right, which is smaller than the element at the current index. Now we know for each index the range in which the current element is minimum. So for each element we can add the product of the current element with the range in which it is minimum in. This way we get the sum of minimum elements for all subarrays. We can do the same for maximum elements for all subarrays.