Sum of minimum elements of all subarrays | CPP implementation of above approach ; Function to return required minimum sum ; getting number of element strictly larger than A [ i ] on Left . ; get elements from stack until element greater than A [ i ] found ; getting number of element larger than A [ i ] on Right . ; get elements from stack until element greater or equal to A [ i ] found ; calculating required resultult ; Driver program ; function call to get required resultult
#include <bits/stdc++.h> NEW_LINE using namespace std ; int sumSubarrayMins ( int A [ ] , int n ) { int left [ n ] , right [ n ] ; stack < pair < int , int > > s1 , s2 ; for ( int i = 0 ; i < n ; ++ i ) { int cnt = 1 ; while ( ! s1 . empty ( ) && ( s1 . top ( ) . first ) > A [ i ] ) { cnt += s1 . top ( ) . second ; s1 . pop ( ) ; } s1 . push ( { A [ i ] , cnt } ) ; left [ i ] = cnt ; } for ( int i = n - 1 ; i >= 0 ; -- i ) { int cnt = 1 ; while ( ! s2 . empty ( ) && ( s2 . top ( ) . first ) >= A [ i ] ) { cnt += s2 . top ( ) . second ; s2 . pop ( ) ; } s2 . push ( { A [ i ] , cnt } ) ; right [ i ] = cnt ; } int result = 0 ; for ( int i = 0 ; i < n ; ++ i ) result = ( result + A [ i ] * left [ i ] * right [ i ] ) ; return result ; } int main ( ) { int A [ ] = { 3 , 1 , 2 , 4 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << sumSubarrayMins ( A , n ) ; return 0 ; }