Maximum Sum Increasing Subsequence | DP | maxSumIS ( ) returns the maximum sum of increasing subsequence in arr [ ] of size n ; Initialize msis values for all indexes ; Compute maximum sum values in bottom up manner ; Pick maximum of all msis values ; Driver Code
def maxSumIS ( arr , n ) : NEW_LINE INDENT max = 0 NEW_LINE msis = [ 0 for x in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT msis [ 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 ] and msis [ i ] < msis [ j ] + arr [ i ] ) : NEW_LINE INDENT msis [ i ] = msis [ j ] + arr [ i ] NEW_LINE DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if max < msis [ i ] : NEW_LINE INDENT max = msis [ i ] NEW_LINE DEDENT DEDENT return max NEW_LINE DEDENT arr = [ 1 , 101 , 2 , 3 , 100 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Sum ▁ of ▁ maximum ▁ sum ▁ increasing ▁ " + " subsequence ▁ is ▁ " + str ( maxSumIS ( arr , n ) ) ) NEW_LINE