Hi! I have been trying the following problem for some time now and haven't been able to come up with a solution better than O(N^2).
Given an array A with N integers, define maxi, j to be the maximum value in A[i..j] and mini, j to be the minimum value in A[i..j]. A[i..j] denotes the subarray starting from index i and ending at j. Compute the following sum:
Please let me know if this problem is available on some OJ.