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
function decompose ( S ) { let s = [ ] ; let N = S . length ; let ans = 0 ; let nix = Number . MAX_VALUE ; for ( let i = N - 1 ; i >= 0 ; i -- ) { if ( s . length == 0 ) { s . push ( S [ i ] ) ; nix = S [ i ] ; } else { if ( S [ i ] < s [ s . length - 1 ] ) { s . push ( S [ i ] ) ; nix = Math . min ( nix , S [ i ] ) ; } else { let val = S [ i ] ; while ( s . length != 0 && val >= s [ s . length - 1 ] ) { s . pop ( ) ; } nix = Math . min ( nix , S [ i ] ) ; s . push ( nix ) ; } } ans += s . length ; } return ans ; } let S = [ ] ; S . push ( 9 ) ; S . push ( 6 ) ; S . push ( 9 ) ; S . push ( 35 ) ; document . write ( decompose ( S ) ) ;