Maximize sum of K elements selected from a Matrix such that each selected element must be preceded by selected row elements | Java program for the above approach ; 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
import java . util . * ; class GFG { static int max ( int a , int b ) { return a > b ? a : b ; } static int maximumsum ( int arr [ ] [ ] , int K , int N , int M ) { int sum = 0 , maxSum ; int i , j , k ; int [ ] [ ] dp = new int [ K + 1 ] [ N + 1 ] ; 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 ] ; } public static void main ( String [ ] args ) { int arr [ ] [ ] = { { 10 , 10 , 100 , 30 } , { 80 , 50 , 10 , 50 } } ; int N = 2 , M = 4 ; int K = 5 ; System . out . print ( maximumsum ( arr , K , N , M ) ) ; } }