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
#include <bits/stdc++.h> NEW_LINE using namespace std ; long mElementsWithMaxSum ( vector < vector < int > > matrix , int M , int block , vector < vector < int > > dp ) { if ( block == matrix . size ( ) ) 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 ] . size ( ) ; i ++ ) { for ( int j = i ; j < matrix [ block ] . size ( ) ; j ++ ) { if ( j - i + 1 <= M ) { ans = 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 ; } void preComputing ( vector < vector < int > > matrix , int N ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < matrix [ i ] . size ( ) ; j ++ ) { matrix [ i ] [ j ] = ( j > 0 ? matrix [ i ] [ j - 1 ] : 0 ) + matrix [ i ] [ j ] ; } } } void mElementsWithMaxSumUtil ( vector < vector < int > > matrix , int M , int N ) { preComputing ( matrix , N ) ; long sum = 10 ; vector < vector < int > > dp ; dp . resize ( N + 5 ) ; for ( int i = 0 ; i < N + 5 ; i ++ ) for ( int j = 0 ; j < M + 5 ; j ++ ) dp [ i ] . push_back ( -1 ) ; sum += mElementsWithMaxSum ( matrix , M , 0 , dp ) ; cout << sum ; } int main ( ) { int N = 3 ; int M = 4 ; vector < vector < int > > matrix = { { 2 , 3 , 5 } , { -1 , 7 } , { 8 , 10 } } ; mElementsWithMaxSumUtil ( matrix , M , N ) ; }