SumOfSubArrayRanges

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long int mx=INT_MIN;long long int mn=INT_MAX;
        long long int sum=0;
        long long int n=nums.size();
        for(int i=0;i<n-1;i++){
            mx=nums[i];
            mn=nums[i];
            for(int j=i+1;j<n;j++){
                if(nums[j]>mx){
                    mx=nums[j];
                }
                if(nums[j]<mn){
                    mn=nums[j];
                }
                sum=sum+(mx-mn);
            }
        }
        return sum;
    }
};
//since nested for loop is in a dependent for loop 
/*
class Solution {
public:
    
    long long subArrayRanges(vector<int>& nums) {
        int n=nums.size();
        long long sum=0;
        stack<int>st;
        vector<int> minPrev(n,-1),minNext(n,n),maxPrev(n,-1),maxNext(n,n);
        
        for(int i=0;i<n;i++)
        {
            while(!st.empty()&&nums[st.top()]>=nums[i]){st.pop();}
            if(!st.empty()){minPrev[i]=st.top();}
            st.push(i);
        }
        while(!st.empty()){st.pop();}
        for(int i=n-1;i>=0;i--)
        {
            while(!st.empty()&&nums[st.top()]>nums[i]){st.pop();}
            if(!st.empty()){minNext[i]=st.top();}
            st.push(i);
        }
        
         for(int i=0;i<n;i++)
         {
            while(!st.empty()&&nums[st.top()]<=nums[i]){st.pop();}
            if(!st.empty()){maxPrev[i]=st.top();}
            st.push(i);
         }
         while(!st.empty()){st.pop();}
         for(int i=n-1;i>=0;i--)
         {
            while(!st.empty()&&nums[st.top()]<nums[i]){st.pop();}
            if(!st.empty()){maxNext[i]=st.top();}
            st.push(i);
         }
        
        for(int i=0;i<n;i++)
        {
            long long leftMin=i-minPrev[i],rightMin=minNext[i]-i;
            long long leftMax=i-maxPrev[i],rightMax=maxNext[i]-i;
            sum+=(leftMax*rightMax-leftMin*rightMin)*nums[i];
            
        }
        return sum;
    }
};
*/

https://leetcode.com/problems/sum-of-subarray-ranges/