Sum of Subarray Ranges
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.
Return the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Follow-up: Could you find a solution with O(n) time complexity?
Example 1
Input
nums = [1,2,3]Output
4The sum of the ranges over all 6 subarrays is 0 + 0 + 0 + 1 + 1 + 2 = 4.
Example 2
Input
nums = [1,3,3]Output
4The sum of the ranges over all 6 subarrays is 0 + 0 + 0 + 2 + 0 + 2 = 4.
Constraints
- 1 <= nums.length <= 1000
- -10^9 <= nums[i] <= 10^9