Given an array of n integers, consider every one of its contiguous subarrays (including single-element subarrays and the whole array). For each subarray, its range span is its maximum element minus its minimum element (a single-element subarray has span 0). Sum the range span over all contiguous subarrays and print the total.
An efficient solution uses monotonic stacks to compute, for each element, how many subarrays it is the maximum of and how many it is the minimum of, then combines the two contributions.
Line 1: an integer n.
Line 2: n space-separated integers.
A single integer: the sum of the range span over every contiguous subarray.
Example 1
Input
3 1 3 2
Expected
5
Explanation
Subarray spans: [1]=0, [1,3]=2, [1,3,2]=2, [3]=0, [3,2]=1, [2]=0. Their sum is 5.
Example 2
Input
2 5 5
Expected
0
Explanation
All three subarrays [5], [5], [5,5] have max equal to min, so every span is 0 and the total is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →