Minimum deletions in Array to make difference of adjacent elements non | C ++ program for the above approach ; Function for finding minimum deletions so that the array becomes non decreasing and the difference between adjacent elements also becomes non decreasing ; initialize answer to a large value ; generating all subsets ; checking the first condition ; checking the second condition ; if both conditions are satisfied consider the answer for minimum ; Driver code ; Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumDeletions ( int A [ ] , int N ) { int ans = INT_MAX ; for ( int i = 1 ; i < ( 1 << N ) ; i ++ ) { vector < int > temp ; for ( int j = 0 ; j < N ; j ++ ) { if ( ( i & ( 1 << j ) ) != 0 ) { temp . push_back ( A [ j ] ) ; } } int flag = 0 ; for ( int j = 1 ; j < temp . size ( ) ; j ++ ) if ( temp [ j ] < temp [ j - 1 ] ) flag = 1 ; for ( int j = 1 ; j < temp . size ( ) - 1 ; j ++ ) if ( temp [ j ] - temp [ j - 1 ] > temp [ j + 1 ] - temp [ j ] ) flag = 1 ; if ( flag == 0 ) { ans = min ( ans , N - ( int ) temp . size ( ) ) ; } } return ans ; } int main ( ) { int A [ ] = { 1 , 4 , 5 , 7 , 20 , 21 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << minimumDeletions ( A , N ) << endl ; return 0 ; }