Maximize sum of K elements selected from a Matrix such that each selected element must be preceded by selected row elements | 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
function max ( a , b ) { return a > b ? a : b ; } function maximumsum ( arr , K , N , M ) { let sum = 0 , maxSum ; let i , j , k ; let dp = new Array ( K + 1 ) ; for ( i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } for ( i = 0 ; i <= N ; i ++ ) dp [ 0 ] [ i ] = 0 ; for ( i = 0 ; i <= K ; i ++ ) dp [ i ] [ 0 ] = 0 ; for ( i = 1 ; i <= K ; i ++ ) { for ( j = 0 ; j < N ; j ++ ) { sum = 0 ; maxSum = dp [ i ] [ j ] ; for ( k = 1 ; k <= M && k <= i ; k ++ ) { sum += arr [ j ] [ k - 1 ] ; maxSum = Math . max ( maxSum , sum + dp [ i - k ] [ j ] ) ; } dp [ i ] [ j + 1 ] = maxSum ; } } return dp [ K ] [ N ] ; } let arr = [ [ 10 , 10 , 100 , 30 ] , [ 80 , 50 , 10 , 50 ] ] ; let N = 2 , M = 4 ; let K = 5 ; document . write ( maximumsum ( arr , K , N , M ) ) ;