Sum of Subarray Minimums
Advanced
Return the sum of min(subarray) over every contiguous subarray of arr, modulo 10**9 + 7.
For [3, 1, 2, 4] the subarray minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1, whose sum is 17.
The starter code visits every subarray. It is correct but too slow for long arrays.
Examples
Example 1
Input:
sum_subarray_mins([3, 1, 2, 4])
Output:
17
Example 2
Input:
sum_subarray_mins([11, 81, 94, 43, 3])
Output:
444
Constraints
0 <= len(arr) <= 2000001 <= arr[i] <= 30000
Theory
Go to TheoryKeywords
dsa-sheetstack-and-queuemonotonic-stack
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.