Find sum of maximum elements of all possible sub arrays of an array.

Input: arr[] = {1, 3, 2}
Output: 15
All possible sub-arrays are {1}, {2}, {3}, {1, 3}, {3, 2} and {1, 3, 2}
And, the sum of all the maximum elements is 1 + 2 + 3 + 3 + 3 + 3 = 15
Input: arr[] = {3, 1}
Output: 7

Optimized Approach: Using stack

  • Find next greater element for a current element in its left.
  • Find next greater element for a current element in its right.

 

// C++ implementation of the approach
#include <iostream>
#include <stack>
using namespace std;
// Driver code
int main()
{
int n;
cin>>n;
int a[n],L[n],R[n];
for(int i=0;i<n;i++) cin>>a[i];
stack<int>s;
for(int i=0;i<n;i++){
//Before pushing we need to check whether top element is greater than current or not
// stack always in descending order
while(!s.empty() and a[i]>= a[(int) s.top()]) s.pop();
//if element found in stack
if(!s.empty()) L[i]=s.top();
//if no element we need to update the extreme index, Here -1
else L[i]=-1;
//Store the current element always, this might be the solution for any further element.
s.push(i);
}
//pop all the elements to make a fresh stack to reuse it.
while(!s.empty()) s.pop();
for(int i=n-1;i>=0;i–){
while(!s.empty() and a[i]>= a[(int) s.top()]) s.pop();
if(!s.empty()) R[i]=s.top();
else R[i]=n;
s.push(i);
}
longlong ans=0;
//calculate the distance times current element [a,b]=((b-a)-1)*a[i]
for(int i=0;i<n;i++){
cout<<L[i]<<” “<<R[i]<<endl;
ans+=(a[i]*(i-L[i])*(R[i]-i));
}
cout<<ans<<endl;
}