Maximize sum by selecting M elements from the start or end of rows of a Matrix | Java 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
import java . util . * ; public class GFG { public static long mElementsWithMaxSum ( long [ ] [ ] matrix , int M , int block , long [ ] [ ] dp ) { if ( block == matrix . length ) return 0 ; if ( dp [ block ] [ M ] != - 1 ) return dp [ block ] [ M ] ; long ans = mElementsWithMaxSum ( matrix , M , block + 1 , dp ) ; for ( int i = 0 ; i < matrix [ block ] . length ; i ++ ) { for ( int 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 ; } public static void preComputing ( long [ ] [ ] matrix , int N ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < matrix [ i ] . length ; j ++ ) { matrix [ i ] [ j ] = ( j > 0 ? matrix [ i ] [ j - 1 ] : 0 ) + matrix [ i ] [ j ] ; } } } public static void mElementsWithMaxSumUtil ( long [ ] [ ] matrix , int M , int N ) { preComputing ( matrix , N ) ; long dp [ ] [ ] = new long [ N + 5 ] [ M + 5 ] ; for ( long i [ ] : dp ) Arrays . fill ( i , - 1 ) ; long sum = mElementsWithMaxSum ( matrix , M , 0 , dp ) ; System . out . print ( sum ) ; } public static void main ( String args [ ] ) { int N = 3 ; int M = 4 ; long [ ] [ ] matrix = { { 2 , 3 , 5 } , { - 1 , 7 } , { 8 , 10 } } ; mElementsWithMaxSumUtil ( matrix , M , N ) ; } }