Maximize sum of K elements selected from a Matrix such that each selected element must be preceded by selected row elements | Python program for the above approach ; Function to return the maximum of two elements ; Function to find the maximum sum of selecting K elements from the given 2D array arr ; dp table of size ( K + 1 ) * ( N + 1 ) ; Initialize dp [ 0 ] [ i ] = 0 ; Initialize dp [ i ] [ 0 ] = 0 ; Selecting i elements ; Select i elements till jth row ; sum = 0 , to keep track of cummulative elements sum ; Traverse arr [ j ] [ k ] until number of elements until k > i ; Select arr [ j ] [ k - 1 ] th item ; Store the maxSum in dp [ i ] [ j + 1 ] ; Return the maximum sum ; Driver Code ; Function Call
import math ; NEW_LINE def max ( a , b ) : NEW_LINE INDENT if ( a > b ) : NEW_LINE INDENT return a ; NEW_LINE DEDENT else : NEW_LINE INDENT return b ; NEW_LINE DEDENT DEDENT def maximumsum ( arr , K , N , M ) : NEW_LINE INDENT sum = 0 ; NEW_LINE maxSum = 0 ; NEW_LINE dp = [ [ 0 for i in range ( N + 1 ) ] for j in range ( K + 1 ) ] NEW_LINE for i in range ( 0 , N + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = 0 ; NEW_LINE DEDENT for i in range ( 0 , K + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 0 ; NEW_LINE DEDENT for i in range ( 1 , K + 1 ) : NEW_LINE INDENT for j in range ( 0 , N ) : NEW_LINE INDENT sum = 0 ; NEW_LINE maxSum = dp [ i ] [ j ] ; NEW_LINE for k in range ( 1 , i + 1 ) : NEW_LINE INDENT if ( k > M ) : NEW_LINE INDENT break ; NEW_LINE DEDENT sum += arr [ j ] [ k - 1 ] ; NEW_LINE maxSum = max ( maxSum , sum + dp [ i - k ] [ j ] ) ; NEW_LINE DEDENT dp [ i ] [ j + 1 ] = maxSum ; NEW_LINE DEDENT DEDENT return dp [ K ] [ N ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 10 , 10 , 100 , 30 ] , [ 80 , 50 , 10 , 50 ] ] ; NEW_LINE N = 2 ; NEW_LINE M = 4 ; NEW_LINE K = 5 ; NEW_LINE print ( maximumsum ( arr , K , N , M ) ) ; NEW_LINE DEDENT