Maximum Sum possible by selecting X elements from a Matrix based on given conditions | C ++ 14 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int n , m , X ; int maxSum ( vector < vector < int > > grid ) { vector < vector < int > > prefsum ( n , vector < int > ( 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 ] ; } } vector < vector < int > > dp ( n , vector < int > ( X + 1 , INT_MIN ) ) ; for ( int i = 0 ; i < n ; i ++ ) dp [ i ] [ 0 ] = 0 ; for ( int i = 1 ; i <= 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 <= min ( j , m ) ; x ++ ) { dp [ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - x ] + prefsum [ i ] [ x - 1 ] ) ; } } } return dp [ n - 1 ] [ X ] ; } int main ( ) { n = 4 ; m = 4 ; X = 6 ; vector < vector < int > > grid = { { 3 , 2 , 6 , 1 } , { 1 , 9 , 2 , 4 } , { 4 , 1 , 3 , 9 } , { 3 , 8 , 2 , 1 } } ; int ans = maxSum ( grid ) ; cout << ( ans ) ; return 0 ; }