Find whether a subarray is in form of a mountain 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
def preprocess ( arr , N , left , right ) : NEW_LINE INDENT left [ 0 ] = 0 NEW_LINE lastIncr = 0 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if ( arr [ i ] > arr [ i - 1 ] ) : NEW_LINE INDENT lastIncr = i NEW_LINE DEDENT left [ i ] = lastIncr NEW_LINE DEDENT right [ N - 1 ] = N - 1 NEW_LINE firstDecr = N - 1 NEW_LINE i = N - 2 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT if ( arr [ i ] > arr [ i + 1 ] ) : NEW_LINE INDENT firstDecr = i NEW_LINE DEDENT right [ i ] = firstDecr NEW_LINE i -= 1 NEW_LINE DEDENT DEDENT def isSubarrayMountainForm ( arr , left , right , L , R ) : NEW_LINE INDENT return ( right [ L ] >= left [ R ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 2 , 4 , 4 , 6 , 3 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE left = [ 0 for i in range ( N ) ] NEW_LINE right = [ 0 for i in range ( N ) ] NEW_LINE preprocess ( arr , N , left , right ) NEW_LINE L = 0 NEW_LINE R = 2 NEW_LINE if ( isSubarrayMountainForm ( arr , left , right , L , R ) ) : NEW_LINE INDENT print ( " Subarray ▁ is ▁ in ▁ mountain ▁ form " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Subarray ▁ is ▁ not ▁ in ▁ mountain ▁ form " ) NEW_LINE DEDENT L = 1 NEW_LINE R = 3 NEW_LINE if ( isSubarrayMountainForm ( arr , left , right , L , R ) ) : NEW_LINE INDENT print ( " Subarray ▁ is ▁ in ▁ mountain ▁ form " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Subarray ▁ is ▁ not ▁ in ▁ mountain ▁ form " ) NEW_LINE DEDENT DEDENT