Minimum number of elements which are not part of Increasing or decreasing subsequence in array | C ++ 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 . ; Driven Program
#include <bits/stdc++.h> NEW_LINE #define MAX  102 NEW_LINE using namespace std ; int countMin ( int arr [ ] , int dp [ MAX ] [ MAX ] [ MAX ] , int n , int dec , int inc , int i ) { if ( dp [ dec ] [ inc ] [ i ] != -1 ) return dp [ dec ] [ inc ] [ i ] ; if ( i == n ) return 0 ; if ( arr [ i ] < arr [ dec ] ) dp [ dec ] [ inc ] [ i ] = countMin ( arr , dp , n , i , inc , i + 1 ) ; if ( arr [ i ] > arr [ inc ] ) { if ( dp [ dec ] [ inc ] [ i ] == -1 ) dp [ dec ] [ inc ] [ i ] = countMin ( arr , dp , n , dec , i , i + 1 ) ; else dp [ dec ] [ inc ] [ i ] = min ( countMin ( arr , dp , n , dec , i , i + 1 ) , dp [ dec ] [ inc ] [ i ] ) ; } if ( dp [ dec ] [ inc ] [ i ] == -1 ) dp [ dec ] [ inc ] [ i ] = 1 + countMin ( arr , dp , n , dec , inc , i + 1 ) ; else dp [ dec ] [ inc ] [ i ] = min ( 1 + countMin ( arr , dp , n , dec , inc , i + 1 ) , dp [ dec ] [ inc ] [ i ] ) ; return dp [ dec ] [ inc ] [ i ] ; } int wrapper ( int arr [ ] , int n ) { arr [ MAX - 2 ] = INT_MAX ; arr [ MAX - 1 ] = INT_MIN ; int dp [ MAX ] [ MAX ] [ MAX ] ; memset ( dp , -1 , sizeof dp ) ; return countMin ( arr , dp , n , MAX - 2 , MAX - 1 , 0 ) ; } int main ( ) { int n = 12 ; int arr [ MAX ] = { 7 , 8 , 1 , 2 , 4 , 6 , 3 , 5 , 2 , 1 , 8 , 7 } ; cout << wrapper ( arr , n ) << endl ; return 0 ; }