Finding sum of product of maximum and minimum over all subarrays

Revision en2, by Death_Scythe, 2018-01-27 22:03:40

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.

Tags subarray, summation, maximum, minimum

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Death_Scythe 2018-01-27 22:03:40 14
en1 English Death_Scythe 2018-01-27 22:02:48 611 Initial revision (published)