Count index pairs which satisfy the given condition | CPP implementation of the approach ; Function to return the count of required index pairs ; To store the required count ; Array to store the left elements upto which current element is maximum ; Iterating through the whole permutation except first and last element ; If current element can be maximum in a subsegment ; Current maximum ; Iterating for smaller values then current maximum on left of it ; Storing left borders of the current maximum ; Iterating for smaller values then current maximum on right of it ; Condition satisfies ; Return count of subsegments ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Count_Segment ( int p [ ] , int n ) { int count = 0 ; int upto [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) upto [ i ] = 0 ; int j = 0 , curr = 0 ; for ( int i = 1 ; i < n + 1 ; i ++ ) { if ( p [ i ] > p [ i - 1 ] and p [ i ] > p [ i + 1 ] ) { curr = p [ i ] ; j = i - 1 ; while ( j >= 0 and p [ j ] < curr ) { upto [ p [ j ] ] = curr ; j -= 1 ; } j = i + 1 ; while ( j < n and p [ j ] < curr ) { if ( upto [ curr - p [ j ] ] == curr ) count += 1 ; j += 1 ; } } } return count ; } int main ( ) { int p [ ] = { 3 , 4 , 1 , 5 , 2 } ; int n = sizeof ( p ) / sizeof ( p [ 0 ] ) ; cout << ( Count_Segment ( p , n ) ) ; return 0 ; }