Printing Maximum Sum Increasing Subsequence | Utility function to calculate sum of all vector elements ; Function to construct Maximum Sum Increasing Subsequence ; 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 ] ; L [ i ] now stores Maximum Sum Increasing Subsequence of arr [ 0. . i ] that ends with arr [ i ] ;  ; find max ; max will contain result ; Driver Code ; construct and prMax Sum IS of arr
def findSum ( arr ) : NEW_LINE INDENT summ = 0 NEW_LINE for i in arr : NEW_LINE INDENT summ += i NEW_LINE DEDENT return summ NEW_LINE DEDENT def printMaxSumIS ( arr , n ) : NEW_LINE INDENT L = [ [ ] for i in range ( n ) ] NEW_LINE 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 ( findSum ( L [ i ] ) < findSum ( L [ j ] ) ) ) : NEW_LINE INDENT for e in L [ j ] : NEW_LINE INDENT if e not in L [ i ] : NEW_LINE INDENT L [ i ] . append ( e ) NEW_LINE DEDENT DEDENT DEDENT DEDENT L [ i ] . append ( arr [ i ] ) NEW_LINE DEDENT res = L [ 0 ] NEW_LINE DEDENT / * res = L [ 0 ] ; * / NEW_LINE INDENT for x in L : NEW_LINE INDENT if ( findSum ( x ) > findSum ( res ) ) : NEW_LINE INDENT res = x NEW_LINE DEDENT DEDENT for i in res : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT arr = [ 3 , 2 , 6 , 4 , 5 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE printMaxSumIS ( arr , n ) NEW_LINE