331. Sum of Subarray Minimums
Given an array of integers arr of size n, calculate the sum of the minimum value in each (contiguous) subarray of arr. Since the result may be large, return the answer modulo 109 +7.
Example 1:
Input: arr = [3, 1, 2, 5]
Output: 18
Explanation: The minimum of subarrays: [3], [1], [2], [5], [3, 1], [1, 2], [2, 5], [3, 1, 2], [1, 2, 5], [3, 1, 2, 5] are 3, 1, 2, 5, 1, 1, 2, 1, 1, 1 respectively and their sum is 18.
Example 2:
Input: arr = [2, 3, 1]
Output: 10
Explanation: The minimum of subarrays: [2], [3], [1], [2,3], [3,1], [2,3,1] are 2, 3, 1, 2, 1, 1 respectively and their sum is 10.
Now Your Turn!
Pick the correct output for the given inputInput: arr = [11, 81, 94, 43, 3]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= arr.length <= 105
- 1 <= arr[i] <= 106