Find whether a subarray is in form of a mountain or not | C ++ program to check whether a subarray is in mountain form or not ; Utility method to construct left and right array ; Initialize first left index as that index only ; if current value is greater than previous , update last increasing ; Initialize last right index as that index only ; if current value is greater than next , update first decreasing ; Method returns true if arr [ L . . R ] is in mountain form ; return true only if right at starting range is greater than left at ending range ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; int preprocess ( int arr [ ] , int N , int left [ ] , int right [ ] ) { left [ 0 ] = 0 ; int lastIncr = 0 ; for ( int i = 1 ; i < N ; i ++ ) { if ( arr [ i ] > arr [ i - 1 ] ) lastIncr = i ; left [ i ] = lastIncr ; } right [ N - 1 ] = N - 1 ; int firstDecr = N - 1 ; for ( int i = N - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] > arr [ i + 1 ] ) firstDecr = i ; right [ i ] = firstDecr ; } } bool isSubarrayMountainForm ( int arr [ ] , int left [ ] , int right [ ] , int L , int R ) { return ( right [ L ] >= left [ R ] ) ; } int main ( ) { int arr [ ] = { 2 , 3 , 2 , 4 , 4 , 6 , 3 , 2 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int left [ N ] , right [ N ] ; preprocess ( arr , N , left , right ) ; int L = 0 ; int R = 2 ; if ( isSubarrayMountainForm ( arr , left , right , L , R ) ) cout << " Subarray ▁ is ▁ in ▁ mountain ▁ form STRNEWLINE " ; else cout << " Subarray ▁ is ▁ not ▁ in ▁ mountain ▁ form STRNEWLINE " ; L = 1 ; R = 3 ; if ( isSubarrayMountainForm ( arr , left , right , L , R ) ) cout << " Subarray ▁ is ▁ in ▁ mountain ▁ form STRNEWLINE " ; else cout << " Subarray ▁ is ▁ not ▁ in ▁ mountain ▁ form STRNEWLINE " ; return 0 ; }