Maximize sum by selecting M elements from the start or end of rows of a Matrix | C # program for the above approach ; 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
using System ; class GFG { public static int mElementsWithMaxSum ( int [ , ] matrix , int M , int block , int [ , ] dp ) { if ( block == matrix . GetLength ( 0 ) ) return 0 ; if ( dp [ block , M ] != - 1 ) return dp [ block , M ] ; int ans = mElementsWithMaxSum ( matrix , M , block + 1 , dp ) ; for ( int i = 0 ; i < GetRow ( matrix , block ) . Length ; i ++ ) { for ( int j = i ; j < GetRow ( 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 ; } public static void preComputing ( int [ , ] matrix , int N ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < GetRow ( matrix , i ) . Length ; j ++ ) { matrix [ i , j ] = ( j > 0 ? matrix [ i , j - 1 ] : 0 ) + matrix [ i , j ] ; } } } public static void mElementsWithMaxSumUtil ( int [ , ] matrix , int M , int N ) { preComputing ( matrix , N ) ; int [ , ] dp = new int [ N + 5 , M + 5 ] ; for ( int i = 0 ; i < N + 5 ; i ++ ) { for ( int j = 0 ; j < M + 5 ; j ++ ) { dp [ i , j ] = - 1 ; } } int sum = mElementsWithMaxSum ( matrix , M , 0 , dp ) ; Console . Write ( sum ) ; } public static int [ ] GetRow ( int [ , ] matrix , int row ) { var rowLength = matrix . GetLength ( 1 ) ; var rowVector = new int [ rowLength ] ; for ( var i = 0 ; i < rowLength ; i ++ ) rowVector [ i ] = matrix [ row , i ] ; return rowVector ; } public static void Main ( String [ ] args ) { int N = 3 ; int M = 4 ; int [ , ] matrix = { { 2 , 3 , 5 } , { - 1 , 7 , 0 } , { 8 , 10 , 0 } } ; mElementsWithMaxSumUtil ( matrix , M , N ) ; } }