Maximize sum of K elements selected from a Matrix such that each selected element must be preceded by selected row elements
Given a 2D array arr[][] of size N * M, and an integer K, the task is to select K elements with maximum possible sum such that if an element arr[i][j] is selected, then all the elements from the ith row present before the jth column needs to be selected.
Examples:
Input: arr[][] = {{10, 10, 100, 30}, {80, 50, 10, 50}}, K = 5
Output: 250
Explanation:
Selecting first 3 elements from the first row, sum = 10 + 10 + 100 = 120
Selecting first 2 elements from the second row, sum = 80 + 50 = 130
Therefore, the maximum sum = 120 + 130 = 250.Input: arr[][] = {{30, 10, 110, 13}, {810, 152, 12, 5}, {124, 24, 54, 124}}, K = 6
Output: 1288
Explanation:
Selecting first 2 elements from the second row, sum = 810 + 152 = 962
Selecting all 4 elements from the third row, sum = 124 + 24 + 54 + 124 = 326
Therefore, the maximum sum = 962 + 326 = 1288
Naive Approach: The simplest approach to solve the problem is to generate all possible subsets of size K from the given matrix based on specified constraint and calculate the maximum sum possible from these subsets.
Time Complexity: O((N*M)!/(K!)*(N*M – K)!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using Dynamic Programming. The idea is to find the maximum sum of selecting i elements till the jth row of the 2D array arr[][]. The auxiliary array dp[i][j + 1] stores the maximum sum of selecting i elements till jth row of matrix arr[][]. Follow the steps below to solve the problem:
- Initialize a dp[][] table of size (K+1)*(N+1) and initialize dp[0][i] as 0, as no elements have sum equal to 0.
- Initialize dp[i][0] as 0, as there are no elements to be selected.
- Iterate over the range [0, K] using two nested loops and [0, N] using the variables i and j respectively:
- Initialize a variable, say sum as 0, to keep track of the cumulative sum of elements in the jth row of arr[][].
- Initialize maxSum as dp[i][j], if no item needs to be selected from jth row of arr[][].
- Iterate with k as 1 until k > M or k > i:
- Increment sum += buy[j][k – 1].
- Store the maximum of existing maxSum and (sum + dp[i – k][j]) in maxSum.
- Store dp[i][j + 1] as the value of maxSum.
- Print the value dp[K][N] as the maximum sum of K elements till (N – 1)th row of matrix arr[][].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to return the maximum // of two elements int max( int a, int b) { return a > b ? a : b; } // Function to find the maximum sum // of selecting K elements from // the given 2D array arr[][] int maximumsum( int arr[][4], int K, int N, int M) { int sum = 0, maxSum; int i, j, k; // dp table of size (K+1)*(N+1) int dp[K + 1][N + 1]; // Initialize dp[0][i] = 0 for (i = 0; i <= N; i++) dp[0][i] = 0; // Initialize dp[i][0] = 0 for (i = 0; i <= K; i++) dp[i][0] = 0; // Selecting i elements for (i = 1; i <= K; i++) { // Select i elements till jth row for (j = 0; j < N; j++) { // dp[i][j+1] is the maximum // of selecting i elements till // jth row // sum = 0, to keep track of // cumulative elements sum sum = 0; maxSum = dp[i][j]; // Traverse arr[j][k] until // number of elements until k>i for (k = 1; k <= M && k <= i; k++) { // Select arr[j][k - 1]th item sum += arr[j][k - 1]; maxSum = max(maxSum, sum + dp[i - k][j]); } // Store the maxSum in dp[i][j+1] dp[i][j + 1] = maxSum; } } // Return the maximum sum return dp[K][N]; } // Driver Code int main() { int arr[][4] = { { 10, 10, 100, 30 }, { 80, 50, 10, 50 } }; int N = 2, M = 4; int K = 5; // Function Call cout << maximumsum(arr, K, N, M); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to return the maximum // of two elements static int max( int a, int b) { return a > b ? a : b; } // Function to find the maximum sum // of selecting K elements from // the given 2D array arr[][] static int maximumsum( int arr[][], int K, int N, int M) { int sum = 0 , maxSum; int i, j, k; // dp table of size (K+1)*(N+1) int [][] dp = new int [K + 1 ][N + 1 ]; // Initialize dp[0][i] = 0 for (i = 0 ; i <= N; i++) dp[ 0 ][i] = 0 ; // Initialize dp[i][0] = 0 for (i = 0 ; i <= K; i++) dp[i][ 0 ] = 0 ; // Selecting i elements for (i = 1 ; i <= K; i++) { // Select i elements till jth row for (j = 0 ; j < N; j++) { // dp[i][j+1] is the maximum // of selecting i elements till // jth row // sum = 0, to keep track of // cumulative elements sum sum = 0 ; maxSum = dp[i][j]; // Traverse arr[j][k] until // number of elements until k>i for (k = 1 ; k <= M && k <= i; k++) { // Select arr[j][k - 1]th item sum += arr[j][k - 1 ]; maxSum = Math.max(maxSum, sum + dp[i - k][j]); } // Store the maxSum in dp[i][j+1] dp[i][j + 1 ] = maxSum; } } // Return the maximum sum return dp[K][N]; } // Driver Code public static void main(String[] args) { int arr[][] = { { 10 , 10 , 100 , 30 }, { 80 , 50 , 10 , 50 } }; int N = 2 , M = 4 ; int K = 5 ; // Function Call System.out.print(maximumsum(arr, K, N, M)); } } // This code is contributed by susmitakundugoaldanga |
Python3
# Python program for the above approach import math; # Function to return the maximum # of two elements def max (a, b): if (a > b): return a; else : return b; # Function to find the maximum sum # of selecting K elements from # the given 2D array arr def maximumsum(arr, K, N, M): sum = 0 ; maxSum = 0 ; # dp table of size (K+1)*(N+1) dp = [[ 0 for i in range (N + 1 )] for j in range (K + 1 )] # Initialize dp[0][i] = 0 for i in range ( 0 , N + 1 ): dp[ 0 ][i] = 0 ; # Initialize dp[i][0] = 0 for i in range ( 0 , K + 1 ): dp[i][ 0 ] = 0 ; # Selecting i elements for i in range ( 1 , K + 1 ): # Select i elements till jth row for j in range ( 0 , N): # dp[i][j+1] is the maximum # of selecting i elements till # jth row # sum = 0, to keep track of # cumulative elements sum sum = 0 ; maxSum = dp[i][j]; # Traverse arr[j][k] until # number of elements until k>i for k in range ( 1 , i + 1 ): if (k > M): break ; # Select arr[j][k - 1]th item sum + = arr[j][k - 1 ]; maxSum = max (maxSum, sum + dp[i - k][j]); # Store the maxSum in dp[i][j+1] dp[i][j + 1 ] = maxSum; # Return the maximum sum return dp[K][N]; # Driver Code if __name__ = = '__main__' : arr = [[ 10 , 10 , 100 , 30 ], [ 80 , 50 , 10 , 50 ]]; N = 2 ; M = 4 ; K = 5 ; # Function Call print (maximumsum(arr, K, N, M)); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; class GFG{ // Function to return the maximum // of two elements static int max( int a, int b) { return a > b ? a : b; } // Function to find the maximum sum // of selecting K elements from // the given 2D array [,]arr static int maximumsum( int [,]arr, int K, int N, int M) { int sum = 0, maxSum; int i, j, k; // dp table of size (K+1)*(N+1) int [,] dp = new int [K + 1, N + 1]; // Initialize dp[0,i] = 0 for (i = 0; i <= N; i++) dp[0, i] = 0; // Initialize dp[i,0] = 0 for (i = 0; i <= K; i++) dp[i, 0] = 0; // Selecting i elements for (i = 1; i <= K; i++) { // Select i elements till jth row for (j = 0; j < N; j++) { // dp[i,j+1] is the maximum // of selecting i elements till // jth row // sum = 0, to keep track of // cumulative elements sum sum = 0; maxSum = dp[i, j]; // Traverse arr[j,k] until // number of elements until k>i for (k = 1; k <= M && k <= i; k++) { // Select arr[j,k - 1]th item sum += arr[j, k - 1]; maxSum = Math.Max(maxSum, sum + dp[i - k, j]); } // Store the maxSum in dp[i,j+1] dp[i, j + 1] = maxSum; } } // Return the maximum sum return dp[K, N]; } // Driver Code public static void Main(String[] args) { int [,]arr = { { 10, 10, 100, 30 }, { 80, 50, 10, 50 } }; int N = 2, M = 4; int K = 5; // Function Call Console.Write(maximumsum(arr, K, N, M)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program to implement // the above approach // Function to return the maximum // of two elements function max(a, b) { return a > b ? a : b; } // Function to find the maximum sum // of selecting K elements from // the given 2D array arr[][] function maximumsum(arr, K, N, M) { let sum = 0, maxSum; let i, j, k; // dp table of size (K+1)*(N+1) let dp = new Array(K + 1); // Loop to create 2D array using 1D array for ( i = 0; i < dp.length; i++) { dp[i] = new Array(2); } // Initialize dp[0][i] = 0 for (i = 0; i <= N; i++) dp[0][i] = 0; // Initialize dp[i][0] = 0 for (i = 0; i <= K; i++) dp[i][0] = 0; // Selecting i elements for (i = 1; i <= K; i++) { // Select i elements till jth row for (j = 0; j < N; j++) { // dp[i][j+1] is the maximum // of selecting i elements till // jth row // sum = 0, to keep track of // cumulative elements sum sum = 0; maxSum = dp[i][j]; // Traverse arr[j][k] until // number of elements until k>i for (k = 1; k <= M && k <= i; k++) { // Select arr[j][k - 1]th item sum += arr[j][k - 1]; maxSum = Math.max(maxSum, sum + dp[i - k][j]); } // Store the maxSum in dp[i][j+1] dp[i][j + 1] = maxSum; } } // Return the maximum sum return dp[K][N]; } // Driver code let arr = [[ 10, 10, 100, 30 ], [ 80, 50, 10, 50 ]]; let N = 2, M = 4; let K = 5; // Function Call document.write(maximumsum(arr, K, N, M)); // This code is contributed by souravghosh0416. </script> |
250
Time Complexity: O(K*N*M)
Auxiliary Space: O(K*N)