Sum of minimum elements of all subarrays | 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
function sumSubarrayMins ( A , n ) { var left = Array ( n ) , right = Array ( n ) ; var s1 = [ ] , s2 = [ ] ; for ( var i = 0 ; i < n ; ++ i ) { var cnt = 1 ; while ( s1 . length != 0 && ( s1 [ s1 . length - 1 ] [ 0 ] ) > A [ i ] ) { cnt += s1 [ s1 . length - 1 ] [ 1 ] ; s1 . pop ( ) ; } s1 . push ( [ A [ i ] , cnt ] ) ; left [ i ] = cnt ; } for ( var i = n - 1 ; i >= 0 ; -- i ) { var cnt = 1 ; while ( s2 . length != 0 && ( s2 [ s2 . length - 1 ] [ 0 ] ) >= A [ i ] ) { cnt += s2 [ s2 . length - 1 ] [ 1 ] ; s2 . pop ( ) ; } s2 . push ( [ A [ i ] , cnt ] ) ; right [ i ] = cnt ; } var result = 0 ; for ( var i = 0 ; i < n ; ++ i ) result = ( result + A [ i ] * left [ i ] * right [ i ] ) ; return result ; } var A = [ 3 , 1 , 2 , 4 ] ; var n = A . length ; document . write ( sumSubarrayMins ( A , n ) ) ;