Sum of decomposition values of all suffixes of an Array | Python3 implementation to find the sum of Decomposition values of all suffixes of an array ; Function to find the decomposition values of the array ; Stack ; Variable to maintain min value in stack ; Loop to iterate over the array ; Condition to check if the stack is empty ; Condition to check if the top of the stack is greater than the current element ; Loop to pop the element out ; The size of the stack is the max no of subarrays for suffix till index i from the right ; Driver Code
import sys NEW_LINE def decompose ( S ) : NEW_LINE INDENT s = [ ] NEW_LINE N = len ( S ) NEW_LINE ans = 0 NEW_LINE nix = sys . maxsize NEW_LINE for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( len ( s ) == 0 ) : NEW_LINE INDENT s . append ( S [ i ] ) NEW_LINE nix = S [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT if ( S [ i ] < s [ - 1 ] ) : NEW_LINE INDENT s . append ( S [ i ] ) NEW_LINE nix = min ( nix , S [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT val = S [ i ] NEW_LINE while ( len ( s ) != 0 and val >= s [ - 1 ] ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT nix = min ( nix , S [ i ] ) ; NEW_LINE s . append ( nix ) NEW_LINE DEDENT DEDENT ans += len ( s ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = [ 9 , 6 , 9 , 35 ] NEW_LINE print ( decompose ( S ) ) NEW_LINE DEDENT