Count indices where the maximum in the prefix array is less than that in the suffix array | C ++ program for the above approach ; Function to print the count of indices in which the maximum in prefix arrays is less than that in the suffix array ; If size of array is 1 ; pre [ ] : Prefix array suf [ ] : Suffix array ; Stores the required count ; Find the maximum in prefix array ; Find the maximum in suffix array ; Traverse the array ; If maximum in prefix array is less than maximum in the suffix array ; Print the answer ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void count ( int a [ ] , int n ) { if ( n == 1 ) { cout << 0 ; return ; } int pre [ n - 1 ] , suf [ n - 1 ] ; int max = a [ 0 ] ; int ans = 0 , i ; pre [ 0 ] = a [ 0 ] ; for ( i = 1 ; i < n - 1 ; i ++ ) { if ( a [ i ] > max ) max = a [ i ] ; pre [ i ] = max ; } max = a [ n - 1 ] ; suf [ n - 2 ] = a [ n - 1 ] ; for ( i = n - 2 ; i >= 1 ; i -- ) { if ( a [ i ] > max ) max = a [ i ] ; suf [ i - 1 ] = max ; } for ( i = 0 ; i < n - 1 ; i ++ ) { if ( pre [ i ] < suf [ i ] ) ans ++ ; } cout << ans ; } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 8 , 1 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; count ( arr , N ) ; return 0 ; }