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 Code ; function call to get required resultult
def sumSubarrayMins ( A , n ) : NEW_LINE INDENT left , right = [ None ] * n , [ None ] * n NEW_LINE s1 , s2 = [ ] , [ ] NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT cnt = 1 NEW_LINE while len ( s1 ) > 0 and s1 [ - 1 ] [ 0 ] > A [ i ] : NEW_LINE INDENT cnt += s1 [ - 1 ] [ 1 ] NEW_LINE s1 . pop ( ) NEW_LINE DEDENT s1 . append ( [ A [ i ] , cnt ] ) NEW_LINE left [ i ] = cnt NEW_LINE DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT cnt = 1 NEW_LINE while len ( s2 ) > 0 and s2 [ - 1 ] [ 0 ] >= A [ i ] : NEW_LINE INDENT cnt += s2 [ - 1 ] [ 1 ] NEW_LINE s2 . pop ( ) NEW_LINE DEDENT s2 . append ( [ A [ i ] , cnt ] ) NEW_LINE right [ i ] = cnt NEW_LINE DEDENT result = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT result += A [ i ] * left [ i ] * right [ i ] NEW_LINE DEDENT return result NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 3 , 1 , 2 , 4 ] NEW_LINE n = len ( A ) NEW_LINE print ( sumSubarrayMins ( A , n ) ) NEW_LINE DEDENT