Maximum Sum possible by selecting X elements from a Matrix based on given conditions | Java program to implement the above approach ; Function to calculate the maximum possible sum by selecting X elements from the Matrix ; Generate prefix sum of the matrix ; Initialize dp [ ] [ ] ; Maximum possible sum by selecting 0 elements from the first i rows ; If a single row is present ; If elements from the current row is not selected ; Iterate over all possible selections from current row ; Return maximum possible sum ; Driver Code
import java . util . * ; import java . io . * ; class GFG { static int n , m , X ; public static int maxSum ( int [ ] [ ] grid ) { int prefsum [ ] [ ] = new int [ n ] [ m ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int x = 0 ; x < m ; x ++ ) { if ( x == 0 ) prefsum [ i ] [ x ] = grid [ i ] [ x ] ; else prefsum [ i ] [ x ] = prefsum [ i ] [ x - 1 ] + grid [ i ] [ x ] ; } } int dp [ ] [ ] = new int [ n ] [ X + 1 ] ; for ( int dpp [ ] : dp ) Arrays . fill ( dpp , Integer . MIN_VALUE ) ; for ( int i = 0 ; i < n ; i ++ ) dp [ i ] [ 0 ] = 0 ; for ( int i = 1 ; i <= Math . min ( m , X ) ; ++ i ) { dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + grid [ 0 ] [ i - 1 ] ; } for ( int i = 1 ; i < n ; ++ i ) { for ( int j = 1 ; j <= X ; ++ j ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; for ( int x = 1 ; x <= Math . min ( j , m ) ; x ++ ) { dp [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - x ] + prefsum [ i ] [ x - 1 ] ) ; } } } return dp [ n - 1 ] [ X ] ; } public static void main ( String [ ] args ) { n = 4 ; m = 4 ; X = 6 ; int grid [ ] [ ] = { { 3 , 2 , 6 , 1 } , { 1 , 9 , 2 , 4 } , { 4 , 1 , 3 , 9 } , { 3 , 8 , 2 , 1 } } ; int ans = maxSum ( grid ) ; System . out . println ( ans ) ; } }