Sum Every Subarray's Maximum-Minus-Minimum
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
For each nonempty contiguous subarray of `nums`, its range is the largest value minus the smallest value in that subarray. Return the sum of the ranges of all such subarrays as a 64-bit integer. Also address the source's follow-up: can you achieve O(n) time?
```cpp
class Solution {
public:
long long subArrayRanges(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [2,5,1]
Output: 11
Explanation: Singletons contribute zero; the other ranges are 3,4,4.
```
**Example 2:**
```text
nums = [4,4]
Output: 0
Explanation: Every subarray has equal minimum and maximum.
```
### Constraints
- `1 <= nums.length <= 1000`.
- `-10^9 <= nums[i] <= 10^9`.
### Clarifying Questions
Repeated equal values are allowed. The output is the sum over occurrences of subarrays, not distinct subarray texts.
```hint Inspect the structure
How many subarrays assign a fixed index as their chosen maximum if its blocking indices are known?
```
### Reasoning checkpoints
- Include every pair of subarray boundaries exactly once, with singletons contributing zero.
- Handle repeated and negative values without double counting.
- Justify the claimed linear time for the source follow-up and keep intermediate and total arithmetic within 64-bit bounds.
### Optional extensions
For the source follow-up, justify why the total work is linear rather than counting only the number of outer-loop iterations.
Overview: Sum Every Subarray's Maximum-Minus-Minimum. For every nonempty contiguous subarray of nums, compute its maximum minus its minimum. Return the sum of these ranges in a 64-bit integer. Address the source follow-up asking for an O(n)-time solution.
