1
class Solution:
2
    def subArrayRanges(self, nums: List[int]) -> int:
3
        n = len(nums)
4

5
        # the answer will be sum{ Max(subarray) - Min(subarray) } over all possible subarray
6
        # which decomposes to sum{Max(subarray)} - sum{Min(subarray)} over all possible subarray
7
        # so totalsum = maxsum - minsum
8
        # we calculate minsum and maxsum in two different loops
9
        minsum = maxsum = 0
10

11
        # first calculate sum{ Min(subarray) } over all subarrays
12
        # sum{ Min(subarray) } = sum(f(i) * nums[i]) ; i=0..n-1
13
        # where f(i) is number of subarrays where nums[i] is the minimum value
14
        # f(i) = (i - index of the previous smaller value) * (index of the next smaller value - i) * nums[i]
15
        # we can claculate these indices in linear time using a monotonically increasing stack.
16
        stack = []
17
        for next_smaller in range(n + 1):
18
            # we pop from the stack in order to satisfy the monotonically increasing order property
19
            # if we reach the end of the iteration and there are elements present in the stack, we pop all of them
20
            while stack and (next_smaller == n or nums[stack[-1]] > nums[next_smaller]):
21
                i = stack.pop()
22
                prev_smaller = stack[-1] if stack else -1
23
                minsum += nums[i] * (next_smaller - i) * (i - prev_smaller)
24
            stack.append(next_smaller)
25

26
        # then calculate sum{ Max(subarray) } over all subarrays
27
        # sum{ Max(subarray) } = sum(f'(i) * nums[i]) ; i=0..n-1
28
        # where f'(i) is number of subarrays where nums[i] is the maximum value
29
        # f'(i) = (i - index of the previous larger value) - (index of the next larger value - i) * nums[i]
30
        # this time we use a monotonically decreasing stack.
31
        stack = []
32
        for next_larger in range(n + 1):
33
            # we pop from the stack in order to satisfy the monotonically decreasing order property
34
            # if we reach the end of the iteration and there are elements present in the stack, we pop all of them
35
            while stack and (next_larger == n or nums[stack[-1]] < nums[next_larger]):
36
                i = stack.pop()
37
                prev_larger = stack[-1] if stack else -1
38
                maxsum += nums[i] * (next_larger - i) * (i - prev_larger)
39
            stack.append(next_larger)
40

41
        return maxsum - minsum