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
from typing import List NEW_LINE def findLIS ( arr : List [ int ] , n : int ) -> List [ int ] : NEW_LINE INDENT L = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT L [ i ] = [ ] NEW_LINE DEDENT L [ 0 ] . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ i ] > arr [ j ] and ( len ( L [ i ] ) < len ( L [ j ] ) ) ) : NEW_LINE INDENT L [ i ] = L [ j ] . copy ( ) NEW_LINE DEDENT DEDENT L [ i ] . append ( arr [ i ] ) NEW_LINE DEDENT maxSize = 1 NEW_LINE lis : List [ int ] = [ ] NEW_LINE for x in L : NEW_LINE INDENT if ( len ( x ) > maxSize ) : NEW_LINE INDENT lis = x . copy ( ) NEW_LINE maxSize = len ( x ) NEW_LINE DEDENT DEDENT return lis NEW_LINE DEDENT def minimize ( input : List [ int ] , n : int ) -> None : NEW_LINE INDENT arr = input . copy ( ) NEW_LINE while len ( arr ) : NEW_LINE INDENT lis = findLIS ( arr , len ( arr ) ) NEW_LINE if ( len ( lis ) < 2 ) : NEW_LINE INDENT break NEW_LINE DEDENT i = 0 NEW_LINE while i < len ( arr ) and len ( lis ) > 0 : NEW_LINE INDENT if ( arr [ i ] == lis [ 0 ] ) : NEW_LINE INDENT arr . remove ( arr [ i ] ) NEW_LINE i -= 1 NEW_LINE lis . remove ( lis [ 0 ] ) NEW_LINE DEDENT i += 1 NEW_LINE DEDENT DEDENT i = 0 NEW_LINE while i < len ( arr ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE i += 1 NEW_LINE DEDENT if ( i == 0 ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT input = [ 3 , 2 , 6 , 4 , 5 , 1 ] NEW_LINE n = len ( input ) NEW_LINE minimize ( input , n ) NEW_LINE DEDENT