Posted on

## Submission

```class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
long long ret = 0;
int n = nums.size();

for(int i = 0; i < n; ++i) {
int minVal = nums[i], maxVal = nums[i];
for(int j = i; j < n; ++j) {
minVal = min(minVal, nums[j]);
maxVal = max(maxVal, nums[j]);
ret += maxVal - minVal;
}
}

return ret;
}
};

// 4,-2,-3,4,1

// -2,-3,4,1```

## Submission with Monotonic Stack

```class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
vector<long long> stk;
int n = nums.size();
vector<long long> leftMin(n), rightMin(n);
vector<long long> leftMax(n), rightMax(n);
long long sumMin = 0, sumMax = 0;

for(int i = 0; i < n; ++i) {
while(!stk.empty() && nums[stk.back()] > nums[i]) stk.pop_back();
if(stk.empty()) leftMin[i] = -1;
else leftMin[i] = stk.back();
stk.push_back(i);
}

stk.clear();

for(int i = n - 1; i >= 0; --i) {
while(!stk.empty() && nums[stk.back()] >= nums[i]) stk.pop_back();
if(stk.empty()) rightMin[i] = n;
else rightMin[i] = stk.back();
stk.push_back(i);
}

stk.clear();

for(int i = 0; i < n; ++i) {
while(!stk.empty() && nums[stk.back()] < nums[i]) stk.pop_back();
if(stk.empty()) leftMax[i] = -1;
else leftMax[i] = stk.back();
stk.push_back(i);
}

stk.clear();

for(int i = n - 1; i >= 0; --i) {
while(!stk.empty() && nums[stk.back()] <= nums[i]) stk.pop_back();
if(stk.empty()) rightMax[i] = n;
else rightMax[i] = stk.back();
stk.push_back(i);
}

long long ret = 0;
for(int i = 0; i < n; ++i) {
ret += nums[i] * ((rightMax[i] - i) * (i - leftMax[i] ) - (rightMin[i] - i) * (i - leftMin[i]));
}

return ret;
}
};

// sum of max - sum of min
//            i
// X 0 [7 6 (1) 3] 0 X

// for a number x at index i, how many numbers can it cover as maximum or minimum value?```