Given a matrix G[][] of dimensions N × M, consists of positive integers, the task is to select X elements from the matrix having maximum sum considering the condition that G[i][j] can only be selected from the matrix unless all the elements G[i][k] are selected, where 0 ? k < j i.e., the jth element in the current ith row can be selected all its the preceding elements of the current ith row has already been selected.
Examples:
Input: N = 4, M = 4, X = 6, G[][] = {{3, 2, 6, 1}, {1, 9, 2, 4}, {4, 1, 3, 9}, {3, 8, 2, 1}}
Output: 28
Explanation:
Selecting the first element from the 1st row = 3
Selecting the first two elements from the 2nd row = 1 + 9 = 10
Selecting the first element from the 3rd row = 4
Selecting the first two elements from the 4th row = 3 + 8 = 11
Hence, the selected elements are {G[0][0], G[1][0], G[1][1], G[2][0], G[3][0], G[3][1]}
Hence, the sum of the selected elements is = 3 + 10 + 4 + 11 = 28Input: N = 2, M = 4, X = 4, G[][] = {{10, 10, 100, 30}, {80, 50, 10, 50}}
Output: 200
Naive Approach: The simplest approach to solve this problem is to calculate the sum for all possible M selections and find the maximum sum among them.
Time Complexity: O(NM)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using Dynamic Programming. The considerable states are:
- Number of rows selected: i.
- Number of elements selected: j.
Initialize a matrix dp[][] such that dp[i][j] stores the maximum possible sum that can be obtained by selecting j elements from the first i rows.
The transition for the dp[][] is as follows:
dp[i][j] = maxx=(0, min(j, m))(dp[i – 1][j – x] + prefsum[i][x])
where prefsum[i][x] is the sum of the first x elements in the ith row of the matrix.
Below is the implementation of above approach:
C++14
// C++14 program to implement // the above approach #include <bits/stdc++.h>using namespace std;int n, m, X;// Function to calculate the maximum// possible sum by selecting X elements// from the Matrixint maxSum(vector<vector<int>> grid){ // Generate prefix sum of the matrix 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)); // Maximum possible sum by selecting // 0 elements from the first i rows for(int i = 0; i < n; i++) dp[i][0] = 0; // If a single row is present 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) { // If elements from the // current row is not selected dp[i][j] = dp[i - 1][j]; // Iterate over all possible // selections from current row 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 maximum possible sum return dp[n - 1][X];}// Driver codeint 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;}// This code is contributed by mohit kumar 29 |
Java
// Java program to implement// the above approachimport java.util.*;import java.io.*;class GFG { static int n, m, X; // Function to calculate the maximum // possible sum by selecting X elements // from the Matrix public static int maxSum(int[][] grid) { // Generate prefix sum of the matrix 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]; // Initialize dp[][] for (int dpp[] : dp) Arrays.fill(dpp, Integer.MIN_VALUE); // Maximum possible sum by selecting // 0 elements from the first i rows for (int i = 0; i < n; i++) dp[i][0] = 0; // If a single row is present 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) { // If elements from the // current row is not selected dp[i][j] = dp[i - 1][j]; // Iterate over all possible // selections from current row 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 maximum possible sum return dp[n - 1][X]; } // Driver Code 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); }} |
Python3
# Python3 program to implement# the above approachimport sys# Function to calculate the maximum# possible sum by selecting X elements# from the Matrixdef maxSum(grid): # Generate prefix sum of the matrix prefsum = [[0 for x in range(m)] for y in range(m)] for i in range(n): for x in range(m): if (x == 0): prefsum[i][x] = grid[i][x] else: prefsum[i][x] = (prefsum[i][x - 1] + grid[i][x]) dp = [[-sys.maxsize - 1 for x in range(X + 1)] for y in range(n)] # Maximum possible sum by selecting # 0 elements from the first i rows for i in range(n): dp[i][0] = 0 # If a single row is present for i in range(1, min(m, X)): dp[0][i] = (dp[0][i - 1] + grid[0][i - 1]) for i in range(1, n): for j in range(1, X + 1): # If elements from the # current row is not selected dp[i][j] = dp[i - 1][j] # Iterate over all possible # selections from current row for x in range(1, min(j, m) + 1): dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + prefsum[i][x - 1]) # Return maximum possible sum return dp[n - 1][X]# Driver Codeif __name__ == "__main__": n = 4 m = 4 X = 6 grid = [ [ 3, 2, 6, 1 ], [ 1, 9, 2, 4 ], [ 4, 1, 3, 9 ], [ 3, 8, 2, 1 ] ] ans = maxSum(grid) print(ans)# This code is contributed by chitranayal |
C#
// C# program to implement // the above approach using System;class GFG{ static int n, m, X; // Function to calculate the maximum // possible sum by selecting X elements // from the Matrix public static int maxSum(int[,] grid) { // Generate prefix sum of the matrix 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]; // Initialize [,]dp for(int i = 1; i < n; i++) for(int j = 1; j <= X; ++j) dp[i, j] = int.MinValue; // Maximum possible sum by selecting // 0 elements from the first i rows for(int i = 0; i < n; i++) dp[i, 0] = 0; // If a single row is present 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) { // If elements from the // current row is not selected dp[i, j] = dp[i - 1, j]; // Iterate over all possible // selections from current row 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 maximum possible sum return dp[n - 1, X]; } // Driver Code 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); Console.WriteLine(ans); } } // This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approachlet n, m, X; // Function to calculate the maximum // possible sum by selecting X elements // from the Matrix function maxSum(grid) { // Generate prefix sum of the matrix let prefsum = new Array(n); // Loop to create 2D array using 1D array for (var i = 0; i < prefsum.length; i++) { prefsum[i] = new Array(2); } for (let i = 0; i < n; i++) { for (let 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]; } } let dp = new Array(n); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for (var i = 0; i < n; i++) { for (var j = 0; j < X+1; j++) { dp[i][j] = 0; } } // Maximum possible sum by selecting // 0 elements from the first i rows for (let i = 0; i < n; i++) dp[i][0] = 0; // If a single row is present for (let i = 1; i <= Math.min(m, X); ++i) { dp[0][i] = dp[0][i - 1] + grid[0][i - 1]; } for (let i = 1; i < n; ++i) { for (let j = 1; j <= X; ++j) { // If elements from the // current row is not selected dp[i][j] = dp[i - 1][j]; // Iterate over all possible // selections from current row for (let 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 maximum possible sum return dp[n - 1][X]; } // Driver Code n = 4; m = 4; X = 6; let grid = [[ 3, 2, 6, 1 ], [ 1, 9, 2, 4 ], [ 4, 1, 3, 9 ], [ 3, 8, 2, 1 ]]; let ans = maxSum(grid); document.write(ans); </script> |
Output:
28
Time Complexity: O(N*M*X)
Auxiliary Space: O(N*M)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
