Size of array after repeated deletion of LIS | C ++ program to find size of array after repeated deletion of LIS ; Function to construct Maximum Sum LIS ; L [ i ] - The Maximum Sum Increasing Subsequence that ends with arr [ i ] ; L [ 0 ] is equal to arr [ 0 ] ; start from index 1 ; for every j less than i ; L [ i ] = { MaxSum ( L [ j ] ) } + arr [ i ] where j < i and arr [ j ] < arr [ i ] ; L [ i ] ends with arr [ i ] ; set lis = LIS whose size is max among all ; The > sign makes sure that the LIS ending first is chose . ; Function to minimize array ; Find LIS of current array ; If all elements are in decreasing order ; Remove lis elements from current array . Note that both lis [ ] and arr [ ] are sorted in increasing order . ; If first element of lis [ ] is found ; Remove lis element from arr [ ] ; Erase first element of lis [ ] ; print remaining element of array ; print - 1 for empty array ; Driver function ; minimize array after deleting LIS
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > findLIS ( vector < int > arr , int n ) { vector < vector < int > > L ( n ) ; L [ 0 ] . push_back ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr [ i ] > arr [ j ] && ( L [ i ] . size ( ) < L [ j ] . size ( ) ) ) L [ i ] = L [ j ] ; } L [ i ] . push_back ( arr [ i ] ) ; } int maxSize = 1 ; vector < int > lis ; for ( vector < int > x : L ) { if ( x . size ( ) > maxSize ) { lis = x ; maxSize = x . size ( ) ; } } return lis ; } void minimize ( int input [ ] , int n ) { vector < int > arr ( input , input + n ) ; while ( arr . size ( ) ) { vector < int > lis = findLIS ( arr , arr . size ( ) ) ; if ( lis . size ( ) < 2 ) break ; for ( int i = 0 ; i < arr . size ( ) && lis . size ( ) > 0 ; i ++ ) { if ( arr [ i ] == lis [ 0 ] ) { arr . erase ( arr . begin ( ) + i ) ; i -- ; lis . erase ( lis . begin ( ) ) ; } } } int i ; for ( i = 0 ; i < arr . size ( ) ; i ++ ) cout << arr [ i ] << " ▁ " ; if ( i == 0 ) cout << " - 1" ; } int main ( ) { int input [ ] = { 3 , 2 , 6 , 4 , 5 , 1 } ; int n = sizeof ( input ) / sizeof ( input [ 0 ] ) ; minimize ( input , n ) ; return 0 ; }