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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define int  long long int NEW_LINE int decompose ( vector < int > S ) { stack < int > s ; int N = S . size ( ) ; int ans = 0 ; int nix = INT_MAX ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( s . empty ( ) ) { s . push ( S [ i ] ) ; nix = S [ i ] ; } else { if ( S [ i ] < s . top ( ) ) { s . push ( S [ i ] ) ; nix = min ( nix , S [ i ] ) ; } else { int val = S [ i ] ; while ( ! s . empty ( ) && val >= s . top ( ) ) { s . pop ( ) ; } nix = min ( nix , S [ i ] ) ; s . push ( nix ) ; } } ans += s . size ( ) ; } return ans ; } signed main ( ) { vector < int > S = { 9 , 6 , 9 , 35 } ; cout << decompose ( S ) << endl ; return 0 ; }