Sum Every Segment Minimum Multiplied by Its Segment Sum
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
For every nonempty contiguous subarray of `strength`, multiply its minimum value by the sum of its values. Add these products for all subarrays and return the total modulo `10^9 + 7`.
```cpp
class Solution {
public:
int totalStrength(vector<int>& strength);
};
```
### Examples
**Example 1:**
```text
Input: strength = [2,2]
Output: 16
Explanation: The singleton contributions are 4 and 4; the whole interval contributes 2*(2+2)=8, totaling 16.
```
**Example 2:**
```text
Input: strength = [3,1]
Output: 14
Explanation: The singletons contribute 9 and 1, while the whole interval contributes 1*(3+1)=4, totaling 14.
```
### Constraints
- `1 <= strength.length <= 100000`.
- `1 <= strength[i] <= 10^9`.
### Clarifying Questions
- Do equal-looking subarrays at different positions count separately? Yes; each index interval contributes once.
- Are empty subarrays included? No.
- Is the minimum multiplied by the length? No; multiply it by the sum of the values.
- What is returned? A single total reduced modulo `10^9 + 7`.
```hint Check the boundary
Check a two-element array with equal values: it has three nonempty index intervals.
```
Overview: Sum each nonempty subarray minimum multiplied by that subarray’s sum, counting index intervals separately and returning the result modulo 1,000,000,007.
