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 elementsint 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 Codeint 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 elementsstatic 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 Codepublic 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 approachimport math;# Function to return the maximum# of two elementsdef 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 arrdef 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 Codeif __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 elementsstatic 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 [,]arrstatic 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 Codepublic 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 elementsfunction 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> |
Output:
250
Time Complexity: O(K*N*M)
Auxiliary Space: O(K*N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
