human
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"
How can the above be solved in Python?
assistant
#Here is code to maximum sum increasing subsequence from a prefix and a given element after prefix is must and the other steps required.
 def pre_compute ( a , n , index , k ) :
	dp = [ [ 0 for i in range ( n ) ] for i in range ( n ) ]
	for i in range ( n ) :
		if a [ i ] > a [ 0 ] :
			dp [ 0 ] [ i ] = a [ i ] + a [ 0 ]
		else :
			dp [ 0 ] [ i ] = a [ i ]
	for i in range ( 1 , n ) :
		for j in range ( n ) :
			if a [ j ] > a [ i ] and j > i :
				if dp [ i - 1 ] [ i ] + a [ j ] > dp [ i - 1 ] [ j ] :
					dp [ i ] [ j ] = dp [ i - 1 ] [ i ] + a [ j ]
				else :
					dp [ i ] [ j ] = dp [ i - 1 ] [ j ]
			else :
				dp [ i ] [ j ] = dp [ i - 1 ] [ j ]
	return dp [ index ] [ k ]
a = [ 1 , 101 , 2 , 3 , 100 , 4 , 5 ]
n = len ( a )
index = 4
k = 6
print ( pre_compute ( a , n , index , k ) )