Size of array after repeated deletion of LIS | Java program to find size of array after repeated deletion of LIS ; Function to conMaximum 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
import java . util . * ; class GFG { static Vector < Integer > findLIS ( Vector < Integer > arr , int n ) { Vector < Integer > [ ] L = new Vector [ n ] ; for ( int i = 0 ; i < L . length ; i ++ ) L [ i ] = new Vector < Integer > ( ) ; L [ 0 ] . add ( arr . elementAt ( 0 ) ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr . elementAt ( i ) > arr . elementAt ( j ) && ( L [ i ] . size ( ) < L [ j ] . size ( ) ) ) L [ i ] = L [ j ] ; } L [ i ] . add ( arr . elementAt ( i ) ) ; } int maxSize = 1 ; Vector < Integer > lis = new Vector < > ( ) ; for ( Vector < Integer > x : L ) { if ( x . size ( ) > maxSize ) { lis = x ; maxSize = x . size ( ) ; } } return lis ; } static void minimize ( int input [ ] , int n ) { Vector < Integer > arr = new Vector < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) arr . add ( input [ i ] ) ; while ( arr . size ( ) != 0 ) { Vector < Integer > lis = findLIS ( arr , arr . size ( ) ) ; if ( lis . size ( ) < 2 ) break ; for ( int i = 0 ; i < arr . size ( ) && lis . size ( ) > 0 ; i ++ ) { if ( arr . elementAt ( i ) == lis . elementAt ( 0 ) ) { arr . removeAll ( lis ) ; i -- ; lis . remove ( 0 ) ; } } } int i ; for ( i = 1 ; i < arr . size ( ) ; i ++ ) System . out . print ( arr . elementAt ( i ) + " ▁ " ) ; if ( i == 0 ) System . out . print ( " - 1" ) ; } public static void main ( String [ ] args ) { int input [ ] = { 3 , 2 , 6 , 4 , 5 , 1 } ; int n = input . length ; minimize ( input , n ) ; } }