Maximize sum of K elements selected from a Matrix such that each selected element must be preceded by selected row elements

0 0 8 minutes read

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 i^th row present before the j^th 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 j^th row of the 2D array arr[][]. The auxiliary array dp[i][j + 1] stores the maximum sum of selecting i elements till j^th 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 j^th row of arr[][].
- Initialize maxSum as dp[i][j], if no item needs to be selected from j^th 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>

Output:

Time Complexity: O(K*N*M)
Auxiliary Space: O(K*N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!