Sum of decomposition values of all suffixes of an Array | C # 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
using System ; using System . Collections . Generic ; class GFG { static int decompose ( List < int > S ) { Stack < int > s = new Stack < int > ( ) ; int N = S . Count ; int ans = 0 ; int nix = Int32 . MaxValue ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( s . Count == 0 ) { s . Push ( S [ i ] ) ; nix = S [ i ] ; } else { if ( S [ i ] < s . Peek ( ) ) { s . Push ( S [ i ] ) ; nix = Math . Min ( nix , S [ i ] ) ; } else { int val = S [ i ] ; while ( s . Count != 0 && val >= s . Peek ( ) ) { s . Pop ( ) ; } nix = Math . Min ( nix , S [ i ] ) ; s . Push ( nix ) ; } } ans += s . Count ; } return ans ; } static void Main ( ) { List < int > S = new List < int > ( ) ; S . Add ( 9 ) ; S . Add ( 6 ) ; S . Add ( 9 ) ; S . Add ( 35 ) ; Console . WriteLine ( decompose ( S ) ) ; } }