680. Sum of Subarray Ranges

HardStack Monotonic Stack Array

The range of a contiguous subarray is its maximum element minus its minimum element. Given an array nums, return the sum of ranges over all non-empty contiguous subarrays. The input is JSON {nums}.

Input: JSON {nums}.

Output: Integer — the sum of all subarray ranges.

Examples

Example 1

Input: {"nums":[1,2,3]}
Output: 4
Explanation: Sum of (max-min) over all subarrays.

Example 2

Input: {"nums":[4,-2,-3,4,1]}
Output: 59
Explanation: Sum over all subarrays.

Example 3

Input: {"nums":[5]}
Output: 0
Explanation: A single element has range 0.

Constraints

1<=n<=1000

Asked by

Amazon Apple Microsoft Google Meta Bloomberg

Solve this problem in the editor →