Return the sum of the range of every contiguous subarray, where range = maximum value minus minimum value.
Given an integer array nums, consider every contiguous subarray of nums. For each subarray, compute its range as:
Return the sum of the ranges of all contiguous subarrays.
The task is to aggregate the contribution of every subarray, not to list the subarrays themselves.
Input Format
- A single integer array
nums. nums[i]is an integer value.
Output Format
- Return one integer: the sum of
max(subarray) - min(subarray)over all contiguous subarrays ofnums.
Constraints
- The array may contain duplicate values.
- The answer may exceed 32-bit integer range, so use a 64-bit type in implementation.
- A solution better than brute force is expected for interview-style use.
Example 1
Input
nums = [1,2,3]
Output
4
Explanation
All subarrays and ranges are: [1]→0, [2]→0, [3]→0, [1,2]→1, [2,3]→1, [1,2,3]→2. Sum = 4.
Example 2
Input
nums = [1,3,3]
Output
4
Explanation
Ranges are: [1]→0, [3]→0, [3]→0, [1,3]→2, [3,3]→0, [1,3,3]→2. Sum = 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.