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 ; Given N ; Given M ; Given matrix ; Function call
function mElementsWithMaxSum ( matrix , M , block , dp ) { if ( block == matrix . length ) return 0 ; if ( dp [ block ] [ M ] != - 1 ) return dp [ block ] [ M ] ; var ans = mElementsWithMaxSum ( matrix , M , block + 1 , dp ) ; for ( var i = 0 ; i < matrix [ block ] . length ; i ++ ) { for ( var j = i ; j < matrix [ block ] . length ; j ++ ) { if ( j - i + 1 <= M ) { ans = Math . max ( ans , matrix [ block ] [ j ] - ( ( i - 1 ) >= 0 ? matrix [ block ] [ i - 1 ] : 0 ) + mElementsWithMaxSum ( matrix , M - j + i - 1 , block + 1 , dp ) ) ; } } } return dp [ block ] [ M ] = ans ; } function preComputing ( matrix , N ) { for ( var i = 0 ; i < N ; i ++ ) { for ( var j = 0 ; j < matrix [ i ] . length ; j ++ ) { matrix [ i ] [ j ] = ( j > 0 ? matrix [ i ] [ j - 1 ] : 0 ) + matrix [ i ] [ j ] ; } } } function mElementsWithMaxSumUtil ( matrix , M , N ) { preComputing ( matrix , N ) ; var dp = Array . from ( Array ( N + 5 ) , ( ) => Array ( M + 5 ) . fill ( - 1 ) ) ; var sum = mElementsWithMaxSum ( matrix , M , 0 , dp ) ; document . write ( sum ) ; } var N = 3 ; var M = 4 ; var matrix = [ [ 2 , 3 , 5 ] , [ - 1 , 7 ] , [ 8 , 10 ] ] ; mElementsWithMaxSumUtil ( matrix , M , N ) ;