Maximize sum by selecting M elements from the start or end of rows of a Matrix | Function to select m elements having maximum sum ; Base case ; If precomputed subproblem occurred ; Either skip the current row ; Iterate through all the possible segments of current row ; Check if it is possible to select elements from i to j ; Compuete the sum of i to j as calculated ; Store the computed answer and return ; Function to precompute the prefix sum for every row of the matrix ; Preprocessing to calculate sum from i to j ; Utility function to select m elements having maximum sum ; Preprocessing step ; Initialize dp array with - 1 ; Stores maximum sum of M elements ; Driver Code ; Given N ; Given M ; Given matrix ; Function call
def mElementsWithMaxSum ( matrix , M , block , dp ) : NEW_LINE INDENT if block == len ( matrix ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ block ] [ M ] != - 1 ) : NEW_LINE INDENT return dp [ block ] [ M ] NEW_LINE DEDENT ans = mElementsWithMaxSum ( matrix , M , block + 1 , dp ) NEW_LINE for i in range ( len ( matrix [ block ] ) ) : NEW_LINE INDENT for j in range ( i , len ( matrix [ block ] ) ) : NEW_LINE INDENT if ( j - i + 1 <= M ) : NEW_LINE INDENT x = 0 NEW_LINE if i - 1 >= 0 : NEW_LINE INDENT x = matrix [ block ] [ i - 1 ] NEW_LINE DEDENT ans = max ( ans , matrix [ block ] [ j ] - x + mElementsWithMaxSum ( matrix , M - j + i - 1 , block + 1 , dp ) ) NEW_LINE DEDENT DEDENT DEDENT dp [ block ] [ M ] = ans NEW_LINE return ans NEW_LINE DEDENT def preComputing ( matrix , N ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( len ( matrix [ i ] ) ) : NEW_LINE INDENT if j > 0 : NEW_LINE INDENT matrix [ i ] [ j ] = matrix [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT return matrix NEW_LINE DEDENT def mElementsWithMaxSumUtil ( matrix , M , N ) : NEW_LINE INDENT matrix = preComputing ( matrix , N ) NEW_LINE sum = 20 NEW_LINE dp = [ [ - 1 for i in range ( M + 5 ) ] for i in range ( N + 5 ) ] NEW_LINE sum += mElementsWithMaxSum ( matrix , M , 0 , dp ) NEW_LINE print ( sum ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE M = 4 NEW_LINE matrix = [ [ 2 , 3 , 5 ] , [ - 1 , 7 ] , [ 8 , 10 ] ] NEW_LINE mElementsWithMaxSumUtil ( matrix , M , N ) NEW_LINE DEDENT