Solution: Sum of Subarray Ranges

Statement

Given an integer array nums, consider every non empty contiguous subarray of nums. For each such subarray, define its range as the difference between its maximum element and its minimum element.

Return the sum of these ranges over all non empty contiguous subarrays of nums.

Note: A follow up asks whether you can solve this in $O(n)$ time.

Constraints:

• ...