Maximize sum of all elements which are not a part of the Longest Increasing Subsequence | Function to find maximum sum ; Find total sum of array ; Maintain a 2D array ; Update the dp array along with sum in the second row ; In case of greater length update the length along with sum ; In case of equal length find length update length with minimum sum ; Find the sum that need to be subtracted from total sum ; Return the sum ; Driver code
def findSum ( arr , n ) : NEW_LINE INDENT totalSum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT totalSum += arr [ i ] NEW_LINE DEDENT dp = [ [ 0 ] * n for i in range ( 2 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT dp [ 0 ] [ i ] = 1 NEW_LINE dp [ 1 ] [ i ] = arr [ i ] NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ i ] > arr [ j ] ) : NEW_LINE INDENT if ( dp [ 0 ] [ i ] < dp [ 0 ] [ j ] + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ j ] + 1 NEW_LINE dp [ 1 ] [ i ] = dp [ 1 ] [ j ] + arr [ i ] NEW_LINE DEDENT elif ( dp [ 0 ] [ i ] == dp [ 0 ] [ j ] + 1 ) : NEW_LINE INDENT dp [ 1 ] [ i ] = min ( dp [ 1 ] [ i ] , dp [ 1 ] [ j ] + arr [ i ] ) NEW_LINE DEDENT DEDENT DEDENT DEDENT maxm = 0 NEW_LINE subtractSum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( dp [ 0 ] [ i ] > maxm ) : NEW_LINE INDENT maxm = dp [ 0 ] [ i ] NEW_LINE subtractSum = dp [ 1 ] [ i ] NEW_LINE DEDENT elif ( dp [ 0 ] [ i ] == maxm ) : NEW_LINE INDENT subtractSum = min ( subtractSum , dp [ 1 ] [ i ] ) NEW_LINE DEDENT DEDENT return totalSum - subtractSum NEW_LINE DEDENT arr = [ 4 , 6 , 1 , 2 , 3 , 8 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findSum ( arr , n ) ) NEW_LINE