2104. Sum of Subarray Ranges Medium

1/**
2 * [2104] Sum of Subarray Ranges
3 *
4 * 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.
5 * Return the sum of all subarray ranges of nums.
6 * A subarray is a contiguous non-empty sequence of elements within an array.
7 *  
8 * Example 1:
9 * 
10 * Input: nums = [1,2,3]
11 * Output: 4
12 * Explanation: The 6 subarrays of nums are the following:
13 * [1], range = largest - smallest = 1 - 1 = 0 
14 * [2], range = 2 - 2 = 0
15 * [3], range = 3 - 3 = 0
16 * [1,2], range = 2 - 1 = 1
17 * [2,3], range = 3 - 2 = 1
18 * [1,2,3], range = 3 - 1 = 2
19 * So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.
20 * Example 2:
21 * 
22 * Input: nums = [1,3,3]
23 * Output: 4
24 * Explanation: The 6 subarrays of nums are the following:
25 * [1], range = largest - smallest = 1 - 1 = 0
26 * [3], range = 3 - 3 = 0
27 * [3], range = 3 - 3 = 0
28 * [1,3], range = 3 - 1 = 2
29 * [3,3], range = 3 - 3 = 0
30 * [1,3,3], range = 3 - 1 = 2
31 * So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.
32 * 
33 * Example 3:
34 * 
35 * Input: nums = [4,-2,-3,4,1]
36 * Output: 59
37 * Explanation: The sum of all subarray ranges of nums is 59.
38 * 
39 *  
40 * Constraints:
41 * 
42 * 	1 <= nums.length <= 1000
43 * 	-10^9 <= nums[i] <= 10^9
44 * 
45 *  
46 * Follow-up: Could you find a solution with O(n) time complexity?
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/sum-of-subarray-ranges/
52// discuss: https://leetcode.com/problems/sum-of-subarray-ranges/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
58        
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_2104() {
70    }
71}
72