Sum of decomposition values of all suffixes of an Array | Java 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 java . util . * ; class GFG { static int decompose ( Vector < Integer > S ) { Stack < Integer > s = new Stack < Integer > ( ) ; int N = S . size ( ) ; int ans = 0 ; int nix = Integer . MAX_VALUE ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( s . isEmpty ( ) ) { s . add ( S . get ( i ) ) ; nix = S . get ( i ) ; } else { if ( S . get ( i ) < s . peek ( ) ) { s . add ( S . get ( i ) ) ; nix = Math . min ( nix , S . get ( i ) ) ; } else { int val = S . get ( i ) ; while ( ! s . isEmpty ( ) && val >= s . peek ( ) ) { s . pop ( ) ; } nix = Math . min ( nix , S . get ( i ) ) ; s . add ( nix ) ; } } ans += s . size ( ) ; } return ans ; } public static void main ( String args [ ] ) { Vector < Integer > S = new Vector < Integer > ( ) ; S . add ( 9 ) ; S . add ( 6 ) ; S . add ( 9 ) ; S . add ( 35 ) ; System . out . println ( decompose ( S ) ) ; } }