Given a matrix of size N X N, the task is to find maximum sum of this Matrix where each value picked is from a unique column for every row.
Examples:
Input: matrix = [[3, 4, 4, 4],
[1, 3, 4, 4],
[3, 2, 3, 4],
[4, 4, 4, 4]]
Output: 16
Explanation:
Selecting (0, 1) from row 1 = 4
Selecting (1, 2) from row 2 = 4
Selecting (2, 3) from row 3 = 4
Selecting (3, 0) from row 4 = 4
Therefore, max sum = 4 + 4 + 4 + 4 = 16
Input: matrix = [[0, 1, 0, 1],
[3, 0, 0, 2],
[1, 0, 2, 0],
[0, 2, 0, 0]]
Output: 8
Explanation:
Selecting (0, 3) from row 1 = 1
Selecting (1, 0) from row 2 = 3
Selecting (2, 2) from row 3 = 2
Selecting (3, 1) from row 4 = 2
Therefore, max sum = 1 + 3 + 2 + 2 = 8
Approach:
- Generate a numeric string of size N containing numbers from 1 to N
- Find the permutation of this string (N!).
- Now pairing is done between the permutations, such that each N! pairing has a unique column for every row.
- Then calculate the sum of values for all the pairs.
Below is the implementation of the above approach:
C++
// C++ code for maximum sum of// a Matrix where each value is// from a unique row and column#include <algorithm>#include <iostream>#include <string>#include <vector>using namespace std;// Function to find the maximum sum in matrixvoid MaxSum(int side, vector<vector<int> > matrix){ string s; for (int i = 0; i < side; i++) { s += to_string(i); } // Permutations of s string vector<string> cases; do { cases.push_back(s); } while (next_permutation(s.begin(), s.end())); // List to store all sums vector<int> sum; // Iterate over all cases for (auto c : cases) { vector<int> p; int tot = 0; for (int i = 0; i < side; i++) { p.push_back(matrix[i] - '0']); } sort(p.begin(), p.end()); for (int i = side - 1; i >= 0; i--) { tot += p[i]; } sum.push_back(tot); } // Maximum of sum list is the max sum cout << *max_element(sum.begin(), sum.end()) << endl;}// Driver codeint main(){ int side = 4; vector<vector<int> > matrix = { { 3, 4, 4, 4 }, { 1, 3, 4, 4 }, { 3, 2, 3, 4 }, { 4, 4, 4, 4 } }; MaxSum(side, matrix); side = 3; matrix = { { 1, 2, 3 }, { 6, 5, 4 }, { 7, 9, 8 } }; MaxSum(side, matrix); return 0;}// This code is contributed by rutikbhosale |
Java
import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Scanner;public class Main { // Function to find the maximum sum in matrix public static void maxSum(int side, int[][] matrix) { StringBuilder s = new StringBuilder(); for (int i = 0; i < side; i++) { s.append(i); } // Permutations of s string List<String> cases = new ArrayList<>(); permutation(s.toString(), cases); // List to store all sums List<Integer> sum = new ArrayList<>(); // Iterate over all cases for (String c : cases) { List<Integer> p = new ArrayList<>(); int tot = 0; for (int i = 0; i < side; i++) { p.add(matrix[i]); } Collections.sort(p); for (int i = side - 1; i >= 0; i--) { tot += p.get(i); } sum.add(tot); } // Maximum of sum list is the max sum System.out.println(Collections.max(sum)); } // Function to generate all permutations of a string public static void permutation(String str, List<String> cases) { permutation("", str, cases); } private static void permutation(String prefix, String str, List<String> cases) { int n = str.length(); if (n == 0) { cases.add(prefix); } else { for (int i = 0; i < n; i++) { permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1), cases); } } } // Driver code public static void main(String[] args) { int side = 4; int[][] matrix = { { 3, 4, 4, 4 }, { 1, 3, 4, 4 }, { 3, 2, 3, 4 }, { 4, 4, 4, 4 } }; maxSum(side, matrix); side = 3; matrix = new int[][] { { 1, 2, 3 }, { 6, 5, 4 }, { 7, 9, 8 } }; maxSum(side, matrix); }} |
Python3
# Python code for maximum sum of # a Matrix where each value is # from a unique row and column# Permutations using library functionfrom itertools import permutations# Function MaxSum to find# maximum sum in matrixdef MaxSum(side, matrix): s = '' # Generating the string for i in range(0, side): s = s + str(i) # Permutations of s string permlist = permutations(s) # List all possible case cases = [] # Append all possible case in cases list for perm in list(permlist): cases.append(''.join(perm)) # List to store all Sums sum = [] # Iterate over all case for c in cases: p = [] tot = 0 for i in range(0, side): p.append(matrix[int(s[i])][int(c[i])]) p.sort() for i in range(side-1, -1, -1): tot = tot + p[i] sum.append(tot) # Maximum of sum list is # the max sum print(max(sum)) # Driver code if __name__ == '__main__': side = 4 matrix = [[3, 4, 4, 4], [1, 3, 4, 4], [3, 2, 3, 4], [4, 4, 4, 4]] MaxSum(side, matrix) side = 3 matrix = [[1, 2, 3], [6, 5, 4], [7, 9, 8]] MaxSum(side, matrix) |
C#
using System;using System.Collections.Generic;using System.Linq;public class Gfg{ // Function to find the maximum sum in matrix public static void MaxSum(int side, List<List<int>> matrix) { string s = ""; for (int i = 0; i < side; i++) { s += i.ToString(); } // Permutations of s string List<string> cases = new List<string>(); do { cases.Add(s); } while (NextPermutation(ref s)); // List to store all sums List<int> sum = new List<int>(); // Iterate over all cases foreach (var c in cases) { List<int> p = new List<int>(); int tot = 0; for (int i = 0; i < side; i++) { p.Add(matrix[i][int.Parse(c[i].ToString())]); } p.Sort(); for (int i = side - 1; i >= 0; i--) { tot += p[i]; } sum.Add(tot); } // Maximum of sum list is the max sum Console.WriteLine(sum.Max()); } // Helper function to generate permutations of a string private static bool NextPermutation(ref string s) { char[] a = s.ToCharArray(); int n = a.Length; int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; if (i < 0) return false; int j = n - 1; while (a[j] <= a[i]) j--; char temp = a[i]; a[i] = a[j]; a[j] = temp; Array.Reverse(a, i + 1, n - i - 1); s = new string(a); return true; } // Driver code public static void Main() { int side = 4; List<List<int>> matrix = new List<List<int>> { new List<int> { 3, 4, 4, 4 }, new List<int> { 1, 3, 4, 4 }, new List<int> { 3, 2, 3, 4 }, new List<int> { 4, 4, 4, 4 } }; MaxSum(side, matrix); side = 3; matrix = new List<List<int>> { new List<int> { 1, 2, 3 }, new List<int> { 6, 5, 4 }, new List<int> { 7, 9, 8 } }; MaxSum(side, matrix); }} |
Javascript
// JavaScript code for maximum sum of// a Matrix where each value is// from a unique row and column// Function MaxSum to find// maximum sum in matrixfunction MaxSum(side, matrix) { let s = ''; // Generating the string for (let i = 0; i < side; i++) { s = s + i; } // Permutations of s string let permlist = permutation(s); // List all possible case let cases = []; // Append all possible case in cases list for (let i = 0; i < permlist.length; i++) { cases.push(permlist[i]); } // List to store all Sums let sum = []; // Iterate over all case for (let i = 0; i < cases.length; i++) { let c = cases[i]; let p = []; let tot = 0; for (let j = 0; j < side; j++) { p.push(matrix[s[j]]]); } p.sort(); for (let j = side - 1; j >= 0; j--) { tot = tot + p[j]; } sum.push(tot); } // Maximum of sum list is // the max sum console.log(Math.max(...sum));}// Driver code function main() { let side = 4; let matrix = [ [3, 4, 4, 4], [1, 3, 4, 4], [3, 2, 3, 4], [4, 4, 4, 4] ]; MaxSum(side, matrix); side = 3; matrix = [ [1, 2, 3], [6, 5, 4], [7, 9, 8] ]; MaxSum(side, matrix);}// permutation functionfunction permutation(string) { if (string.length === 0) return []; if (string.length === 1) return [string]; let result = []; for (let i = 0; i < string.length; i++) { let firstChar = string[i]; let charsLeft = string.substring(0, i) + string.substring(i + 1); let innerPermutations = permutation(charsLeft); for (let j = 0; j < innerPermutations.length; j++) { result.push(firstChar + innerPermutations[j]); } } return result;}main();// This code is contributed by Prince Kumar |
Output:
16 18
Time complexity: O(K), where K = N!
Auxiliary Space complexity: O(K), where 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
