Minimum number of elements which are not part of Increasing or decreasing subsequence in array | Python3 program to return minimum number of elements which are not part of increasing or decreasing subsequences . ; Return minimum number of elements which is not part of any of the sequence . ; If already calculated , return value . ; If whole array is traversed . ; calculating by considering element as part of decreasing sequence . ; calculating by considering element as part of increasing sequence . ; If cannot be calculated for decreasing sequence . ; After considering once by decreasing sequence , now try for increasing sequence . ; If element cannot be part of any of the sequence . ; After considering element as part of increasing and decreasing sequence trying as not part of any of the sequence . ; Wrapper Function ; Adding two number at the end of array , so that increasing and decreasing sequence can be made . MAX - 2 index is assigned INT_MAX for decreasing sequence because / next number of sequence must be less than it . Similarly , for Increasing sequence INT_MIN is assigned to MAX - 1 index . ; Driver code
MAX = 102 NEW_LINE def countMin ( arr , dp , n , dec , inc , i ) : NEW_LINE INDENT if dp [ dec ] [ inc ] [ i ] != - 1 : NEW_LINE INDENT return dp [ dec ] [ inc ] [ i ] NEW_LINE DEDENT if i == n : NEW_LINE INDENT return 0 NEW_LINE DEDENT if arr [ i ] < arr [ dec ] : NEW_LINE INDENT dp [ dec ] [ inc ] [ i ] = countMin ( arr , dp , n , i , inc , i + 1 ) NEW_LINE DEDENT if arr [ i ] > arr [ inc ] : NEW_LINE INDENT if dp [ dec ] [ inc ] [ i ] == - 1 : NEW_LINE INDENT dp [ dec ] [ inc ] [ i ] = countMin ( arr , dp , n , dec , i , i + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ dec ] [ inc ] [ i ] = min ( countMin ( arr , dp , n , dec , i , i + 1 ) , dp [ dec ] [ inc ] [ i ] ) NEW_LINE DEDENT DEDENT if dp [ dec ] [ inc ] [ i ] == - 1 : NEW_LINE INDENT dp [ dec ] [ inc ] [ i ] = 1 + countMin ( arr , dp , n , dec , inc , i + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ dec ] [ inc ] [ i ] = min ( 1 + countMin ( arr , dp , n , dec , inc , i + 1 ) , dp [ dec ] [ inc ] [ i ] ) NEW_LINE DEDENT return dp [ dec ] [ inc ] [ i ] NEW_LINE DEDENT def wrapper ( arr , n ) : NEW_LINE INDENT arr [ MAX - 2 ] = 1000000000 NEW_LINE arr [ MAX - 1 ] = - 1000000000 NEW_LINE dp = [ [ [ - 1 for i in range ( MAX ) ] for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE return countMin ( arr , dp , n , MAX - 2 , MAX - 1 , 0 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 12 NEW_LINE arr = [ 7 , 8 , 1 , 2 , 4 , 6 , 3 , 5 , 2 , 1 , 8 , 7 ] NEW_LINE for i in range ( MAX ) : NEW_LINE INDENT arr . append ( 0 ) NEW_LINE DEDENT print ( wrapper ( arr , n ) ) NEW_LINE DEDENT