Given a 2D array Blocks[][] consisting of N rows of variable length. The task is to select at most M elements with the maximum possible sum from Blocks[][] from either the start or end of a row.
Examples:
Input: N = 3, M = 4
Blocks[][] = {{2, 3, 5}, {-1, 7}, {8, 10}}
Output: 30
Explanation:
Select {5} from 1st row.
Select {7} from 2nd row.
Select {8, 10} from 3rd row.Input: N = 3, M = 2
Blocks[][] = {{100, 3, -1}, {-1, 7, 10}, {8, 10, 15}}
Output: 115
Explanation:
select {100} from 1st row.
Skip 2nd row.
Select {15} from 3rd row.
Naive Approach: The simplest approach is to iterate through all the rows of the matrix and push all the elements into a vector and sort it. Calculate the sum of the last M elements and print it as the required answer.
Time Complexity: O(N * KlogK), where K is the maximum size any block can have.
Auxiliary Space: O(N * K)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming using Memoization. Follow the steps below:
- Given N rows and from each row, select any segment from the ith row, say from l to r.
- The count of elements in ith row is (r – l + 1) and proceed to the next row.
- To calculate the maximum sum, use the prefix sum technique in order to calculate the sum.
- Initialize a 2D array dp[][], where dp[N][M] stores the maximum sum by selecting at most M elements from N rows.
- Consider the following two scenarios:
- Either skip the current row.
- Select any segment from the current row that does not exceed the number of elements selected.
- Consider the following two scenarios:
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to select m elements// having maximum sumlong mElementsWithMaxSum(vector<vector<int> > matrix, int M, int block, vector<vector<int> > dp){ // Base case if (block == matrix.size()) return 0; // If precomputed subproblem occurred if (dp[block][M] != -1) return dp[block][M]; // Either skip the current row long ans = mElementsWithMaxSum(matrix, M, block + 1, dp); // Iterate through all the possible // segments of current row for(int i = 0; i < matrix[block].size(); i++) { for(int j = i; j < matrix[block].size(); j++) { // Check if it is possible to select // elements from i to j if (j - i + 1 <= M) { // Compute the sum of i to j as // calculated ans = max(ans, matrix[block][j] - ((i - 1) >= 0 ? matrix[block][i - 1] : 0) + mElementsWithMaxSum(matrix, M - j + i - 1, block + 1, dp)); } } } // Store the computed answer and return return dp[block][M] = ans;}// Function to precompute the prefix sum// for every row of the matrixvoid preComputing(vector<vector<int>> matrix, int N){ // Preprocessing to calculate sum from i to j 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]; } }}// Utility function to select m elements having// maximum sumvoid mElementsWithMaxSumUtil(vector<vector<int>> matrix, int M, int N){ // Preprocessing step preComputing(matrix, N); long sum = 10; // Initialize dp array with -1 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); // Stores maximum sum of M elements sum += mElementsWithMaxSum(matrix, M, 0, dp); cout << sum;}// Driver Codeint main(){ // Given N int N = 3; // Given M int M = 4; // Given matrix vector<vector<int>> matrix = { { 2, 3, 5 }, { -1, 7 }, { 8, 10 } }; // Function call mElementsWithMaxSumUtil(matrix, M, N);}// This code is contributed by grand_master |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Function to select m elements // having maximum sum public static long mElementsWithMaxSum(long[][] matrix, int M, int block, long[][] dp) { // Base case if (block == matrix.length) return 0; // If precomputed subproblem occurred if (dp[block][M] != -1) return dp[block][M]; // Either skip the current row long ans = mElementsWithMaxSum(matrix, M, block + 1, dp); // Iterate through all the possible // segments of current row for (int i = 0; i < matrix[block].length; i++) { for (int j = i; j < matrix[block].length; j++) { // Check if it is possible to select // elements from i to j if (j - i + 1 <= M) { // Compute the sum of i to j as // calculated ans = Math.max( ans, matrix[block][j] - ((i - 1) >= 0 ? matrix[block][i - 1] : 0) + mElementsWithMaxSum( matrix, M - j + i - 1, block + 1, dp)); } } } // Store the computed answer and return return dp[block][M] = ans; } // Function to precompute the prefix sum // for every row of the matrix public static void preComputing(long[][] matrix, int N) { // Preprocessing to calculate sum from i to j for (int i = 0; i < N; i++) { for (int j = 0; j < matrix[i].length; j++) { matrix[i][j] = (j > 0 ? matrix[i][j - 1] : 0) + matrix[i][j]; } } } // Utility function to select m elements having // maximum sum public static void mElementsWithMaxSumUtil(long[][] matrix, int M, int N) { // Preprocessing step preComputing(matrix, N); // Initialize dp array with -1 long dp[][] = new long[N + 5][M + 5]; for (long i[] : dp) Arrays.fill(i, -1); // Stores maximum sum of M elements long sum = mElementsWithMaxSum(matrix, M, 0, dp); // Print the sum System.out.print(sum); } // Driver Code public static void main(String args[]) { // Given N int N = 3; // Given M int M = 4; // Given matrix long[][] matrix = { { 2, 3, 5 }, { -1, 7 }, { 8, 10 } }; // Function Call mElementsWithMaxSumUtil(matrix, M, N); }} |
Python3
# Python3 program for the above approach# Function to select m elements# having maximum sumdef mElementsWithMaxSum(matrix, M, block, dp): # Base case if block == len(matrix): return 0 # If precomputed subproblem occurred if (dp[block][M] != -1): return dp[block][M] # Either skip the current row ans = mElementsWithMaxSum(matrix, M, block + 1, dp) # Iterate through all the possible # segments of current row for i in range(len(matrix[block])): for j in range(i, len(matrix[block])): # Check if it is possible to select # elements from i to j if (j - i + 1 <= M): # Compute the sum of i to j as # calculated x = 0 if i - 1 >= 0: x = matrix[block][i - 1] ans = max(ans, matrix[block][j] - x + mElementsWithMaxSum(matrix, M - j + i - 1, block + 1, dp)) # Store the computed answer and return dp[block][M] = ans return ans# Function to precompute the prefix sum# for every row of the matrixdef preComputing(matrix, N): # Preprocessing to calculate sum from i to j for i in range(N): for j in range(len(matrix[i])): if j > 0: matrix[i][j] = matrix[i][j - 1] return matrix# Utility function to select m elements having# maximum sumdef mElementsWithMaxSumUtil(matrix, M, N): # Preprocessing step matrix = preComputing(matrix, N) sum = 20 # Initialize dp array with -1 dp = [[-1 for i in range(M + 5)] for i in range(N + 5)] # Stores maximum sum of M elements sum += mElementsWithMaxSum(matrix, M, 0, dp) print(sum)# Driver Codeif __name__ == '__main__': # Given N N = 3 # Given M M = 4 # Given matrix matrix = [ [ 2, 3, 5 ], [ -1, 7 ], [ 8, 10 ] ] # Function call mElementsWithMaxSumUtil(matrix, M, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;class GFG{// Function to select m elements// having maximum sumpublic static int mElementsWithMaxSum(int[,] matrix, int M, int block, int[,] dp){// Base caseif (block == matrix.GetLength(0)) return 0;// If precomputed subproblem occurredif (dp[block, M] != -1) return dp[block, M];// Either skip the current rowint ans = mElementsWithMaxSum(matrix, M, block + 1, dp);// Iterate through all the possible// segments of current rowfor (int i = 0; i < GetRow(matrix, block).Length; i++) { for (int j = i; j < GetRow(matrix, block).Length; j++) { // Check if it is possible to select // elements from i to j if (j - i + 1 <= M) { // Compute the sum of i to j as // calculated ans = Math.Max(ans, matrix[block, j] - ((i - 1) >= 0 ? matrix[block, i - 1] : 0) + mElementsWithMaxSum(matrix, M - j + i - 1, block + 1, dp)); } }}// Store the computed answer and returnreturn dp[block, M] = ans;}// Function to precompute the prefix sum// for every row of the matrixpublic static void preComputing(int[,] matrix, int N){// Preprocessing to calculate sum from i to jfor (int i = 0; i < N; i++) { for (int j = 0; j < GetRow(matrix, i).Length; j++) { matrix[i, j] = (j > 0 ? matrix[i, j - 1] : 0) + matrix[i, j]; }}}// Utility function to select // m elements having maximum sumpublic static void mElementsWithMaxSumUtil(int[,] matrix, int M, int N){// Preprocessing steppreComputing(matrix, N);// Initialize dp array with -1int [,]dp = new int[N + 5, M + 5];for(int i = 0; i < N + 5; i++){ for (int j = 0; j < M + 5; j++) { dp[i, j] = -1; }}// Stores maximum sum of M elementsint sum = mElementsWithMaxSum(matrix, M, 0, dp);// Print the sumConsole.Write(sum);}public static int[] GetRow(int[,] matrix, int row){var rowLength = matrix.GetLength(1);var rowVector = new int[rowLength];for (var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i];return rowVector;}// Driver Codepublic static void Main(String []args){// Given Nint N = 3;// Given Mint M = 4;// Given matrixint[,] matrix = {{2, 3, 5}, {-1, 7,0}, {8, 10, 0}};// Function CallmElementsWithMaxSumUtil(matrix, M, N);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function to select m elements// having maximum sumfunction mElementsWithMaxSum(matrix, M, block, dp){ // Base case if (block == matrix.length) return 0; // If precomputed subproblem occurred if (dp[block][M] != -1) return dp[block][M]; // Either skip the current row var ans = mElementsWithMaxSum(matrix, M, block + 1, dp); // Iterate through all the possible // segments of current row for(var i = 0; i < matrix[block].length; i++) { for(var j = i; j < matrix[block].length; j++) { // Check if it is possible to select // elements from i to j if (j - i + 1 <= M) { // Compute the sum of i to j as // calculated ans = Math.max(ans, matrix[block][j] - ((i - 1) >= 0 ? matrix[block][i - 1] : 0) + mElementsWithMaxSum(matrix, M - j + i - 1, block + 1, dp)); } } } // Store the computed answer and return return dp[block][M] = ans;}// Function to precompute the prefix sum// for every row of the matrixfunction preComputing(matrix, N){ // Preprocessing to calculate sum from i to j for(var i = 0; i < N; i++) { for(var j = 0; j < matrix[i].length; j++) { matrix[i][j] = (j > 0 ? matrix[i][j - 1] : 0) + matrix[i][j]; } }}// Utility function to select m elements having// maximum sumfunction mElementsWithMaxSumUtil(matrix, M, N){ // Preprocessing step preComputing(matrix, N); // Initialize dp array with -1 var dp = Array.from(Array(N+5), ()=> Array(M+5).fill(-1)); // Stores maximum sum of M elements var sum = mElementsWithMaxSum(matrix, M, 0, dp); document.write( sum);}// Driver Code// Given Nvar N = 3;// Given Mvar M = 4;// Given matrixvar matrix = [ [ 2, 3, 5 ], [ -1, 7 ], [ 8, 10 ] ];// Function callmElementsWithMaxSumUtil(matrix, M, N);// This code is contributed by noob2000.</script> |
Output:
30
Time Complexity: O(N * M)
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!
