Minimum removals required to convert given array to a Mountain Array | Utility function to count array elements required to be removed to make array a mountain array ; Stores length of increasing subsequence from [ 0 , i - 1 ] ; Stores length of increasing subsequence from [ i + 1 , n - 1 ] ; Iterate for each position up to N - 1 to find the length of subsequence ; If j is less than i , then i - th position has leftIncreasing [ j ] + 1 lesser elements including itself ; Check if it is the maximum obtained so far ; Search for increasing subsequence from right ; Find the position following the peak condition and have maximum leftIncreasing [ i ] + rightIncreasing [ i ] ; Function to count elements to be removed to make array a mountain array ; Print the answer ; Driver Code ; Given array ; Function Call
def minRemovalsUtil ( arr ) : NEW_LINE INDENT result = 0 NEW_LINE if ( len ( arr ) < 3 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT leftIncreasing = [ 0 ] * len ( arr ) NEW_LINE rightIncreasing = [ 0 ] * len ( arr ) NEW_LINE for i in range ( 1 , len ( arr ) ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ j ] < arr [ i ] ) : NEW_LINE INDENT leftIncreasing [ i ] = max ( leftIncreasing [ i ] , leftIncreasing [ j ] + 1 ) ; NEW_LINE DEDENT DEDENT DEDENT for i in range ( len ( arr ) - 2 , - 1 , - 1 ) : NEW_LINE INDENT j = len ( arr ) - 1 NEW_LINE while j > i : NEW_LINE INDENT if ( arr [ j ] < arr [ i ] ) : NEW_LINE INDENT rightIncreasing [ i ] = max ( rightIncreasing [ i ] , rightIncreasing [ j ] + 1 ) NEW_LINE DEDENT j -= 1 NEW_LINE DEDENT DEDENT for i in range ( len ( arr ) ) : NEW_LINE INDENT if ( leftIncreasing [ i ] != 0 and rightIncreasing [ i ] != 0 ) : NEW_LINE INDENT result = max ( result , leftIncreasing [ i ] + rightIncreasing [ i ] ) ; NEW_LINE DEDENT DEDENT return len ( arr ) - ( result + 1 ) NEW_LINE DEDENT def minRemovals ( arr ) : NEW_LINE INDENT ans = minRemovalsUtil ( arr ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 1 , 1 , 5 , 6 , 2 , 3 , 1 ] NEW_LINE minRemovals ( arr ) NEW_LINE DEDENT