Maximum sum increasing subsequence from a prefix and a given element after prefix is must | Python3 program to find maximum sum increasing subsequence till i - th index and including k - th index . ; Initializing the first row of the dp [ ] [ ] ; Creating the dp [ ] [ ] matrix . ; To calculate for i = 4 and k = 6. ; Driver code
def pre_compute ( a , n , index , k ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if a [ i ] > a [ 0 ] : NEW_LINE INDENT dp [ 0 ] [ i ] = a [ i ] + a [ 0 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 0 ] [ i ] = a [ i ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if a [ j ] > a [ i ] and j > i : NEW_LINE INDENT if dp [ i - 1 ] [ i ] + a [ j ] > dp [ i - 1 ] [ j ] : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ i ] + a [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT return dp [ index ] [ k ] NEW_LINE DEDENT a = [ 1 , 101 , 2 , 3 , 100 , 4 , 5 ] NEW_LINE n = len ( a ) NEW_LINE index = 4 NEW_LINE k = 6 NEW_LINE print ( pre_compute ( a , n , index , k ) ) NEW_LINE