Finding sum of product of maximum and minimum over all subarrays

Правка en1, от Death_Scythe, 2018-01-27 22:02:48

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 to be the maximum value in A[i..j] and 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.

Теги subarray, summation, maximum, minimum

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Death_Scythe 2018-01-27 22:03:40 14
en1 Английский Death_Scythe 2018-01-27 22:02:48 611 Initial revision (published)