Sum of Minimums of All Contiguous Subarrays
In data analysis and financial modeling, understanding the behavior of minimum values within various windows or segments of a dataset is a fundamental operation. For instance, identifying the lowest stock price within all possible contiguous trading periods can reveal critical insights into market volatility. This problem challenges you to calculate the cumulative impact of these minimums across all possible contiguous subarrays.
Given an array of integers arr, you need to find the sum of min(b) for every contiguous subarray b of arr. Since the answer may be very large, return it modulo 10^9 + 7.
arr: An array of integers (number[] in TypeScript, Array<number> in JavaScript).10^9 + 7.arr that are adjacent in the original array. For example, for [1,2,3], [1,2] is a contiguous subarray, but [1,3] is not.10^9 + 7 should be applied at each step of the sum calculation to prevent intermediate integer overflow, ensuring the final result remains within representable limits.Examples
Example 1
Input:
arr = [3,1,2,4]
Output:
17
Note:
The contiguous subarrays are: [3], min is 3 [1], min is 1 [2], min is 2 [4], min is 4 [3,1], min is 1 [1,2], min is 1 [2,4], min is 2 [3,1,2], min is 1 [1,2,4], min is 1 [3,1,2,4], min is 1 Sum = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17
Example 2
Input:
arr = [11,81,94,43,3]
Output:
444
Note:
Let's analyze the contribution of each element arr[i] as the minimum in subarrays:
For arr[0] = 11: It's the minimum in 1 subarray to its left (itself) and 4 subarrays to its right (until 3 at index 4). Number of subarrays where 11 is the minimum = (0 - (-1)) * (4 - 0) = 1 * 4 = 4. Contribution = 11 * 4 = 44.
For arr[1] = 81: Previous strictly smaller is 11 (index 0). Next smaller or equal is 43 (index 3). Number of subarrays = (1 - 0) * (3 - 1) = 1 * 2 = 2. Contribution = 81 * 2 = 162.
For arr[2] = 94: Previous strictly smaller is 81 (index 1). Next smaller or equal is 43 (index 3). Number of subarrays = (2 - 1) * (3 - 2) = 1 * 1 = 1. Contribution = 94 * 1 = 94.
For arr[3] = 43: Previous strictly smaller is 11 (index 0). Next smaller or equal is 3 (index 4). Number of subarrays = (3 - 0) * (4 - 3) = 3 * 1 = 3. Contribution = 43 * 3 = 129.
For arr[4] = 3: Previous strictly smaller is no element (index -1). Next smaller or equal is no element (index 5). Number of subarrays = (4 - (-1)) * (5 - 4) = 5 * 1 = 5. Contribution = 3 * 5 = 15.
Total sum = 44 + 162 + 94 + 129 + 15 = 444.
Constraints
1 <= arr.length <= 3 * 10^41 <= arr[i] <= 3 * 10^410^9 + 7.Loading editor...