Given a positive integer K and a matrix arr[][] of dimensions N*M consisting of integers, the task is to find the maximum sum of K elements possible from the given matrix.
Examples:
Input: arr[][] = {10, 10, 100, 30}, {80, 50, 10, 50}}, K = 5
Output: 310
Explanation:
Choose K(= 5) elements from the matrix as {100, 30, 80, 50, 50}, then the sum is 100 + 30 + 80 + 50 + 50 = 310, which is maximum.Input: arr[][] = {80, 80, 15, 50, 20, 10}, K = 3
Output: 210
Naive Approach: The simplest approach to solve the problem is to generate all possible subsets of size K from the matrix and calculate the maximum sum possible from these subsets. Follow the steps below to solve the given problem:
- Sort all arrays in decreasing order in the given matrix mat[].
- Initialize a matrix, prefixSum[][] that stores the prefix sum of each row of the given matrix.
- Define a function, maximumSum() that recursively create all the combinations of K elements and return the maximum sum using the below steps:
- Initialize two variables, say id as 0 and rem as p representing the elements included in the sum and number of elements that need to be included respectively.
- Now in each recursive call perform the following steps:
- Traverse each element in prefixSum[id] and recursive call for the two recursive calls either including or excluding the current value.
- If it includes the current element then, check for all combinations in the arrays below.
- Finally, it will return the maximum weight after taking an element and not taking it.
- After completing the above steps, print the value return by the function maximumSum().
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum sum of K // elements from the matrix int maximumSum(vector<vector< int > >& prefixSum, int K, int N, int rem, int id) { // Stores the maximum sum of K elements int ans = INT_MIN; // Base Case if (rem == 0) return 0; if (id >= N || rem < 0) return INT_MIN; // Iterate over K elements and find // the maximum sum for ( int i = 0; i <= K; i++) { ans = max(ans, prefixSum[id][i] + maximumSum(prefixSum, K, N, rem - i, id + 1)); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K // element from the given matrix void findSum(vector<vector< int > >& arr, int N, int K, int P) { // Stores the prefix sum of the matrix vector<vector< int > > prefixSum(N, vector< int >(K + 1, 0)); // Sorting the arrays for ( int i = 0; i < arr.size(); i++) { sort(arr[i].begin(), arr[i].end(), greater< int >()); } // Storing prefix sum in matrix prefixSum for ( int i = 0; i < N; i++) { int sum = 0; for ( int j = 1; j <= K; j++) { sum += arr[i][j - 1]; prefixSum[i][j] = sum; } } // Print the maximum sum cout << maximumSum(prefixSum, K, N, P, 0); } // Driver Code int main() { vector<vector< int > > arr = { { 80, 80 }, { 15, 50 }, { 20, 10 } }; int N = arr.size(); int M = arr[0].size(); int K = 3; findSum(arr, N, M, K); return 0; } |
Java
import java.util.*; class GFG { // Function to find the maximum sum of K // elements from the matrix static int maximumSum( int [][] prefixSum, int K, int N, int rem, int id) { // Stores the maximum sum of K elements int ans = Integer.MIN_VALUE; // Base Case if (rem == 0 ) return 0 ; if (id >= N || rem < 0 ) return Integer.MIN_VALUE; // Iterate over K elements and find // the maximum sum for ( int i = 0 ; i <= K; i++) { ans = Math.max(ans, prefixSum[id][i] + maximumSum(prefixSum, K, N, rem - i, id + 1 )); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K // element from the given matrix static void findSum(List<List<Integer>> arr, int N, int K, int P) { // Stores the prefix sum of the matrix int [][] prefixSum = new int [N][K + 1 ]; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < K + 1 ; j++) { prefixSum[i][j] = 0 ; } } // Sorting the arrays for ( int i = 0 ; i < arr.size(); i++) { Collections.sort(arr.get(i), Collections.reverseOrder()); } // Storing prefix sum in matrix prefixSum for ( int i = 0 ; i < N; i++) { int sum = 0 ; for ( int j = 1 ; j <= K; j++) { sum += arr.get(i).get(j - 1 ); prefixSum[i][j] = sum; } } // Print the maximum sum System.out.println(maximumSum(prefixSum, K, N, P, 0 )); } public static void main(String[] args) { List<List<Integer>> arr = new ArrayList<>(); arr.add(Arrays.asList( 80 , 80 )); arr.add(Arrays.asList( 15 , 50 )); arr.add(Arrays.asList( 20 , 10 )); int N = arr.size(); int M = arr.get( 0 ).size(); int K = 3 ; findSum(arr, N, M, K); } } |
Python3
# Python3 program for the above approach import sys # Function to find the maximum sum of K # elements from the matrix def maximumSum(prefixSum, K, N, rem, Id ): # Stores the maximum sum of K elements ans = - sys.maxsize # Base Case if rem = = 0 : return 0 if Id > = N or rem < 0 : return - sys.maxsize # Iterate over K elements and find # the maximum sum for i in range (K + 1 ): ans = max (ans, prefixSum[ Id ][i] + maximumSum(prefixSum, K, N, rem - i, Id + 1 )) # Return the maximum sum obtained return ans # Function to find the maximum sum of K # element from the given matrix def findSum(arr, N, K, P): # Stores the prefix sum of the matrix prefixSum = [[ 0 for i in range (K + 1 )] for j in range (N)] # Sorting the arrays for i in range ( len (arr)): arr[i].sort() arr[i].reverse() # Storing prefix sum in matrix prefixSum for i in range (N): Sum = 0 for j in range ( 1 , K + 1 ): Sum + = arr[i][j - 1 ] prefixSum[i][j] = Sum # Print the maximum sum print (maximumSum(prefixSum, K, N, P, 0 )) arr = [ [ 80 , 80 ], [ 15 , 50 ], [ 20 , 10 ] ] N = len (arr) M = len (arr[ 0 ]) K = 3 findSum(arr, N, M, K) # This code is contributed by rameshtravel07. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the maximum sum of K // elements from the matrix static int maximumSum( int [,] prefixSum, int K, int N, int rem, int id) { // Stores the maximum sum of K elements int ans = Int32.MinValue; // Base Case if (rem == 0) return 0; if (id >= N || rem < 0) return Int32.MinValue; // Iterate over K elements and find // the maximum sum for ( int i = 0; i <= K; i++) { ans = Math.Max(ans, prefixSum[id,i] + maximumSum(prefixSum, K, N, rem - i, id + 1)); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K // element from the given matrix static void findSum(List<List< int >> arr, int N, int K, int P) { // Stores the prefix sum of the matrix int [,] prefixSum = new int [N,K + 1]; for ( int i = 0; i < N; i++) { for ( int j = 0; j < K + 1; j++) { prefixSum[i,j] = 0; } } // Sorting the arrays for ( int i = 0; i < arr.Count; i++) { arr[i].Sort(); arr[i].Reverse(); } // Storing prefix sum in matrix prefixSum for ( int i = 0; i < N; i++) { int sum = 0; for ( int j = 1; j <= K; j++) { sum += arr[i][j - 1]; prefixSum[i,j] = sum; } } // Print the maximum sum Console.Write(maximumSum(prefixSum, K, N, P, 0)); } static void Main() { List<List< int >> arr = new List<List< int >>(); arr.Add( new List< int >( new int []{80, 80})); arr.Add( new List< int >( new int []{15, 50})); arr.Add( new List< int >( new int []{20, 10})); int N = arr.Count; int M = arr[0].Count; int K = 3; findSum(arr, N, M, K); } } // This code is contributed by mukesh07. |
Javascript
<script> // Javascript program for the above approach // Function to find the maximum sum of K // elements from the matrix function maximumSum(prefixSum, K, N, rem, id) { // Stores the maximum sum of K elements let ans = Number.MIN_SAFE_INTEGER; // Base Case if (rem == 0) return 0; if (id >= N || rem < 0) return Number.MIN_SAFE_INTEGER; // Iterate over K elements and find // the maximum sum for (let i = 0; i <= K; i++) { ans = Math.max( ans, prefixSum[id][i] + maximumSum(prefixSum, K, N, rem - i, id + 1) ); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K // element from the given matrix function findSum(arr, N, K, P) { // Stores the prefix sum of the matrix let prefixSum = new Array(N).fill(0).map(() => new Array(K + 1).fill(0)); // Sorting the arrays for (let i = 0; i < arr.length; i++) { arr[i].sort((a, b) => -a + b); } // Storing prefix sum in matrix prefixSum for (let i = 0; i < N; i++) { let sum = 0; for (let j = 1; j <= K; j++) { sum += arr[i][j - 1]; prefixSum[i][j] = sum; } } // Print the maximum sum document.write(maximumSum(prefixSum, K, N, P, 0)); } // Driver Code let arr = [ [80, 80], [15, 50], [20, 10], ]; let N = arr.length; let M = arr[0].length; let K = 3; findSum(arr, N, M, K); // This code is contributed by saurabh_jaiswal. </script> |
210
Time Complexity: O(MN)
Auxiliary Space: O(N*M)
Efficient Approach: The above approach can also be optimized by storing the Overlapping Subproblems in a 2D array and use the result of recurring states to reduce the time complexity.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum sum of K // elements from the matrix int maximumSum(vector<vector< int > >& prefixSum, vector<vector< int > >& dp, int K, int N, int rem, int id) { // Stores the maximum sum of K elements int ans = INT_MIN; // Base Case if (rem == 0) return 0; if (id >= N || rem < 0) return INT_MIN; if (dp[id][rem] != -1) return dp[id][rem]; // Iterate over K elements and find // the maximum sum for ( int i = 0; i <= K; i++) { ans = max(ans, prefixSum[id][i] + maximumSum(prefixSum, dp, K, N, rem - i, id + 1)); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K // element from the given matrix void findSum(vector<vector< int > >& arr, int N, int K, int P) { // Stores the prefix sum of the matrix vector<vector< int > > prefixSum(N, vector< int >(K + 1, 0)); vector<vector< int > > dp(N, vector< int >(P + 1, -1)); // Sorting the arrays for ( int i = 0; i < arr.size(); i++) { sort(arr[i].begin(), arr[i].end(), greater< int >()); } // Storing prefix sum in matrix prefixSum for ( int i = 0; i < N; i++) { int sum = 0; for ( int j = 1; j <= K; j++) { sum += arr[i][j - 1]; prefixSum[i][j] = sum; } } // Print the maximum sum cout << maximumSum(prefixSum, dp, K, N, P, 0); } // Driver Code int main() { vector<vector< int > > arr = { { 80, 80 }, { 15, 50 }, { 20, 10 } }; int N = arr.size(); int M = arr[0].size(); int K = 3; findSum(arr, N, M, K); return 0; } |
Java
import java.util.*; import java.io.*; // Java program for the above approach class GFG{ // Function to find the maximum sum of K // elements from the matrix public static int maximumSum(ArrayList<ArrayList<Integer>> prefixSum, ArrayList<ArrayList<Integer>> dp, int K, int N, int rem, int id) { // Stores the maximum sum of K elements int ans = Integer.MIN_VALUE; // Base Case if (rem == 0 ) return 0 ; if (id >= N || rem < 0 ) return ans; if (dp.get(id).get(rem) != - 1 ) return dp.get(id).get(rem); // Iterate over K elements and find // the maximum sum for ( int i = 0 ; i <= K; i++) { ans = Math.max(ans, prefixSum.get(id).get(i) + maximumSum(prefixSum, dp, K, N, rem - i, id + 1 )); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K // element from the given matrix public static void findSum(ArrayList<ArrayList<Integer>> arr, int N, int K, int P) { // Stores the prefix sum of the matrix ArrayList<ArrayList<Integer>> prefixSum = new ArrayList<ArrayList<Integer>>(); for ( int i = 0 ; i < N ; i++){ prefixSum.add( new ArrayList<Integer>()); for ( int j = 0 ; j <= K ; j++){ prefixSum.get(i).add( 0 ); } } ArrayList<ArrayList<Integer>> dp = new ArrayList<ArrayList<Integer>>(); for ( int i = 0 ; i < N ; i++){ dp.add( new ArrayList<Integer>()); for ( int j = 0 ; j <= P ; j++){ dp.get(i).add(- 1 ); } } // Sorting the arrays for ( int i = 0 ; i < arr.size() ; i++) { Collections.sort(arr.get(i)); Collections.reverse(arr.get(i)); } // Storing prefix sum in matrix prefixSum for ( int i = 0 ; i < N; i++) { int sum = 0 ; for ( int j = 1 ; j <= K; j++) { sum += arr.get(i).get(j - 1 ); prefixSum.get(i).set(j, sum); } } // Print the maximum sum System.out.println(maximumSum(prefixSum, dp, K, N, P, 0 )); } // Driver code public static void main(String args[]) { ArrayList<ArrayList<Integer> > arr = new ArrayList<ArrayList<Integer>>( List.of( new ArrayList<Integer>(List.of( 80 , 80 ) ), new ArrayList<Integer>(List.of( 15 , 50 ) ), new ArrayList<Integer>(List.of( 20 , 10 ) ) ) ); int N = arr.size(); int M = arr.get( 0 ).size(); int K = 3 ; findSum(arr, N, M, K); } } // This code is contributed by subhamgoyal2014. |
Python3
import sys # Function to find the maximum sum of K elements from the matrix def maximumSum(prefixSum, dp, K, N, rem, id ): # Stores the maximum sum of K elements ans = - sys.maxsize # Base Case if rem = = 0 : return 0 if id > = N or rem < 0 : return - sys.maxsize if dp[ id ][rem] ! = - 1 : return dp[ id ][rem] # Iterate over K elements and find the maximum sum for i in range (K + 1 ): ans = max (ans, prefixSum[ id ][i] + maximumSum(prefixSum, dp, K, N, rem - i, id + 1 )) # Return the maximum sum obtained return ans # Function to find the maximum sum of K element from the given matrix def findSum(arr, N, K, P): # Stores the prefix sum of the matrix prefixSum = [[ 0 ] * (K + 1 ) for i in range (N)] dp = [[ - 1 ] * (P + 1 ) for i in range (N)] # Sorting the arrays for i in range ( len (arr)): arr[i].sort(reverse = True ) # Storing prefix sum in matrix prefixSum for i in range (N): sum = 0 for j in range ( 1 , K + 1 ): sum + = arr[i][j - 1 ] prefixSum[i][j] = sum # Print the maximum sum print (maximumSum(prefixSum, dp, K, N, P, 0 )) # Driver Code if __name__ = = "__main__" : arr = [[ 80 , 80 ], [ 15 , 50 ], [ 20 , 10 ]] N = len (arr) M = len (arr[ 0 ]) K = 3 findSum(arr, N, M, K) # This code is contributed by Vikram_Shirsat |
Javascript
const INT_MIN = Number.MIN_SAFE_INTEGER; // Function to find the maximum sum of K elements from the matrix function maximumSum(prefixSum, dp, K, N, rem, id) { // Stores the maximum sum of K elements let ans = INT_MIN; // Base Case if (rem === 0) return 0; if (id >= N || rem < 0) return INT_MIN; if (dp[id][rem] !== -1) return dp[id][rem]; // Iterate over K elements and find the maximum sum for (let i = 0; i <= K; i++) { ans = Math.max(ans, prefixSum[id][i] + maximumSum(prefixSum, dp, K, N, rem - i, id + 1)); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K element from the given matrix function findSum(arr, N, K, P) { // Stores the prefix sum of the matrix let prefixSum = []; let dp = []; // Initialize prefixSum and dp arrays for (let i = 0; i < N; i++) { prefixSum.push(Array(K + 1).fill(0)); dp.push(Array(P + 1).fill(-1)); } // Sorting the arrays for (let i = 0; i < arr.length; i++) { arr[i].sort((a, b) => b - a); } // Storing prefix sum in matrix prefixSum for (let i = 0; i < N; i++) { let sum = 0; for (let j = 1; j <= K; j++) { sum += arr[i][j - 1]; prefixSum[i][j] = sum; } } // Print the maximum sum console.log(maximumSum(prefixSum, dp, K, N, P, 0)); } // Driver Code let arr = [[80, 80], [15, 50], [20, 10]]; let N = arr.length; let M = arr[0].length; let K = 3; findSum(arr, N, M, K); |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the maximum sum of K // elements from the matrix static int maximumSum(List<List< int >> prefixSum, List<List< int >> dp, int K, int N, int rem, int id) { // Stores the maximum sum of K elements int ans = int .MinValue; // Base Case if (rem == 0) return 0; if (id >= N || rem < 0) return int .MinValue; if (dp[id][rem] != -1) return dp[id][rem]; // Iterate over K elements and find // the maximum sum for ( int i = 0; i <= K; i++) { ans = Math.Max(ans, prefixSum[id][i] + maximumSum(prefixSum, dp, K, N, rem - i, id + 1)); } // Return the maximum sum obtained return ans; } // Function to find the maximum sum of K // element from the given matrix static void findSum(List<List< int >> arr, int N, int K, int P) { // Stores the prefix sum of the matrix List<List< int >> prefixSum = new List<List< int >>(N); List<List< int >> dp = new List<List< int >>(N); for ( int i = 0; i < N; i++) { prefixSum.Add( new List< int >(K + 1)); dp.Add( new List< int >(P + 1)); for ( int j = 0; j <= K; j++) { prefixSum[i].Add(0); } for ( int j = 0; j <= P; j++) { dp[i].Add(-1); } } // Sorting the arrays for ( int i = 0; i < arr.Count; i++) { arr[i].Sort(); arr[i].Reverse(); } // Storing prefix sum in matrix prefixSum for ( int i = 0; i < N; i++) { int sum = 0; for ( int j = 1; j <= K; j++) { sum += arr[i][j - 1]; prefixSum[i][j] = sum; } } // Print the maximum sum Console.WriteLine(maximumSum(prefixSum, dp, K, N, P, 0)); } // Driver Code static void Main() { List<List< int >> arr = new List<List< int >>{ new List< int >{ 80, 80 }, new List< int >{ 15, 50 }, new List< int >{ 20, 10 } }; int N = arr.Count; int M = arr[0].Count; int K = 3; findSum(arr, N, M, K); } } // This code is contributed by shivamsharma215 |
210
Time Complexity: O(N*M*K)
Auxiliary Space: O(K*N2)
Optimized Approach: The above approach can also be optimized by storing all the matrix elements in another array arr[] and then sort the array in decreasing order and print the sum of the first K elements as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum sum of K // element from the given matrix void maximumSum(vector<vector< int > >& arr, int N, int M, int K) { vector< int > allArr(N * M, 0); // Store all matrix elements int id = 0; for ( int i = 0; i < N; i++) { for ( int j = 0; j < K; j++) { allArr[id] = arr[i][j]; id++; } } // Sort the array sort(allArr.begin(), allArr.end(), greater< int >()); // Stores the maximum sum int ans = 0; // Find the maximum sum for ( int i = 0; i < K; i++) { ans += allArr[i]; } // Print the maximum sum cout << ans; } // Driver Code int main() { vector<vector< int > > arr = { { 80, 80 }, { 15, 50 }, { 20, 10 } }; int N = arr.size(); int M = arr[0].size(); int K = 3; maximumSum(arr, N, M, K); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { static int [][] arr = { { 80 , 80 }, { 15 , 50 }, { 20 , 10 } }; // Function to find the maximum sum of K // element from the given matrix static void maximumSum( int N, int M, int K) { int [] allArr = new int [N * M]; // Store all matrix elements int id = 0 ; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { allArr[id] = arr[i][j]; id++; } } // Sort the array Arrays.sort(allArr); for ( int i = 0 ; i < allArr.length/ 2 ; i++) { int temp = allArr[i]; allArr[i] = allArr[allArr.length -i- 1 ]; allArr[allArr.length -i- 1 ] = temp; } // Stores the maximum sum int ans = 0 ; // Find the maximum sum for ( int i = 0 ; i < K; i++) { ans += allArr[i]; } // Print the maximum sum System.out.print(ans); } // Driver code public static void main(String[] args) { int N = 3 ; int M = 2 ; int K = 3 ; maximumSum(N, M, K); } } // This code is contributed by decode2207. |
Python3
# Python3 program for the above approach arr = [ [ 80 , 80 ], [ 15 , 50 ], [ 20 , 10 ] ] # Function to find the maximum sum of K # element from the given matrix def maximumSum(N, M, K): allArr = [ 0 ] * (N * M) # Store all matrix elements Id = 0 for i in range (N): for j in range (M): allArr[ Id ] = arr[i][j] Id + = 1 # Sort the array allArr.sort() allArr.reverse() # Stores the maximum sum ans = 0 # Find the maximum sum for i in range (K): ans + = allArr[i] # Print the maximum sum print (ans) # Driver code N = 3 M = 2 K = 3 maximumSum(N, M, K) # This code is contributed by suresh07. |
C#
// C# program for the above approach using System; class GFG { static int [,] arr = { { 80, 80 }, { 15, 50 }, { 20, 10 } }; // Function to find the maximum sum of K // element from the given matrix static void maximumSum( int N, int M, int K) { int [] allArr = new int [N * M]; // Store all matrix elements int id = 0; for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { allArr[id] = arr[i,j]; id++; } } // Sort the array Array.Sort(allArr); Array.Reverse(allArr); // Stores the maximum sum int ans = 0; // Find the maximum sum for ( int i = 0; i < K; i++) { ans += allArr[i]; } // Print the maximum sum Console.Write(ans); } // Driver code static void Main() { int N = 3; int M = 2; int K = 3; maximumSum(N, M, K); } } // This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for the above approach let arr = [ [ 80, 80 ], [ 15, 50 ], [ 20, 10 ] ]; // Function to find the maximum sum of K // element from the given matrix function maximumSum(N, M, K) { let allArr = new Array(N * M); allArr.fill(0); // Store all matrix elements let id = 0; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { allArr[id] = arr[i][j]; id++; } } // Sort the array allArr.sort( function (a, b){ return a - b}); allArr.reverse(); // Stores the maximum sum let ans = 0; // Find the maximum sum for (let i = 0; i < K; i++) { ans += allArr[i]; } // Print the maximum sum document.write(ans); } let N = 3; let M = 2; let K = 3; maximumSum(N, M, K); // This code is contributed by divyeshrabadiya07. </script> |
210
Time Complexity: O(N*M*log(N*M))
Auxiliary Space: O(N*M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!