Given a NxM matrix with N rows and M columns of positive integers. The task is to find the sum of pair with maximum sum in the matrix.
Examples:
Input : mat[N][M] = {{1, 2, 3, 4},
{25, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output : 41
Pair (25, 16) has the maximum sum
Input : mat[N][M] = {{1, 2, 3},
{4, 6, 7},
{9, 10, 5}}
Output : 19
Simple Approach: A simple approach is to traverse the matrix twice and find the first maximum and second maximum elements and return their sum.
Better Approach: A better approach is to find the first and second maximum in a single traversal of the matrix.
1) Initialize two variables first and second to INT_MIN as,
first = second = INT_MIN
2) Start traversing the matrix,
a) If the current element in array say mat[i][j] is greater
than first. Then update first and second as,
second = first
first = mat[i][j]
b) If the current element is in between first and second,
then update second to store the value of current variable as
second = mat[i][j]
3) Return sum of both first and second maximum.
Below is the implementation of the above approach:
C++
// C++ program to find maximum sum// pair in a matrix#include <bits/stdc++.h>using namespace std;#define N 4 // Rows#define M 4 // Columns// Function to find maximum sum// pair from matrixint maxSumPair(int mat[N][M]){ int max1 = INT_MIN; // First max int max2 = INT_MIN; // Second max // Traverse the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mat[i][j] > max1) { max2 = max1; // second max = first max max1 = mat[i][j]; // first max = current } // If second max is between current element // and first max else if (mat[i][j] > max2 && mat[i][j] <= max1) { max2 = mat[i][j]; } } } return max1 + max2;}// Driver Codeint main(){ // matrix int mat[N][M] = { { 1, 2, 3, 4 }, { 25, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; cout << maxSumPair(mat) << endl; return 0;} |
Java
// Java program to find maximum sum// pair in a matriximport java.io.*;class GFG { static int N = 4; // Rowsstatic int M = 4; // Columns// Function to find maximum sum// pair from matrixstatic int maxSumPair(int [][]mat){ int max1 = Integer.MIN_VALUE; // First max int max2 = Integer.MIN_VALUE; // Second max // Traverse the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mat[i][j] > max1) { max2 = max1; // second max = first max max1 = mat[i][j]; // first max = current } // If second max is between current element // and first max else if (mat[i][j] > max2 && mat[i][j] <= max1) { max2 = mat[i][j]; } } } return max1 + max2;}// Driver Code public static void main (String[] args) { // matrix int [][]mat = { { 1, 2, 3, 4 }, { 25, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; System.out.println(maxSumPair(mat)); }}// This code is contributed// by shs |
Python3
# Python 3 program to find maximum sum# pair in a matriximport sysN = 4 # RowsM = 4 # Columns# Function to find maximum sum# pair from matrixdef maxSumPair(mat): max1 = -sys.maxsize - 1 # First max max2 = -sys.maxsize - 1 # Second max # Traverse the matrix for i in range(0, N): for j in range (0, M): if (mat[i][j] > max1): max2 = max1 # second max = first max max1 = mat[i][j] # first max = current # If second max is between current # element and first max elif (mat[i][j] > max2 and mat[i][j] <= max1): max2 = mat[i][j] return max1 + max2# Driver Code# matrixmat = [ [1, 2, 3, 4 ], [25, 6, 7, 8 ], [9, 10, 11, 12 ], [13, 14, 15, 16 ]]print(maxSumPair(mat))# This code is contributed # by ihritik |
C#
// C# program to find maximum sum// pair in a matrixusing System; public class GFG { static int N = 4; // Rowsstatic int M = 4; // Columns // Function to find maximum sum// pair from matrixstatic int maxSumPair(int [,]mat){ int max1 = int.MinValue; // First max int max2 = int.MinValue; // Second max // Traverse the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mat[i,j] > max1) { max2 = max1; // second max = first max max1 = mat[i,j]; // first max = current } // If second max is between current element // and first max else if (mat[i,j] > max2 && mat[i,j] <= max1) { max2 = mat[i,j]; } } } return max1 + max2;} // Driver Code public static void Main () { // matrix int [,]mat = { { 1, 2, 3, 4 }, { 25, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; Console.WriteLine(maxSumPair(mat)); }}// This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP program to find maximum sum// pair in a $matrix$N = 4; // Rows$M = 4; // Columns// Function to find maximum sum// pair from $matrixfunction maxSumPair($mat){ global $N; global $M; $max1 = PHP_INT_MIN; // First max $max2 = PHP_INT_MIN; // Second max // Traverse the $matrix for ($i = 0; $i < $N; $i++) { for ($j = 0; $j < $M; $j++) { if ($mat[$i][$j] > $max1) { $max2 = $max1; // second max = first max $max1 = $mat[$i][$j]; // first max = current } // If second max is between current // element and first max else if ($mat[$i][$j] > $max2 && $mat[$i][$j] <= $max1) { $max2 = $mat[$i][$j]; } } } return $max1 + $max2;}// Driver Code// matrix$mat = array(array(1, 2, 3, 4 ), array(25, 6, 7, 8 ), array(9, 10, 11, 12 ), array(13, 14, 15, 16 ));echo maxSumPair($mat);// This code is contributed // by ihritik?> |
Javascript
<script>// JavaScript program to find maximum sum// pair in a matrix var N = 4; // Rowsvar M = 4; // Columns // Function to find maximum sum// pair from matrixfunction maxSumPair(mat){ var max1 = -1000000000; // First max var max2 = -1000000000; // Second max // Traverse the matrix for (var i = 0; i < N; i++) { for (var j = 0; j < M; j++) { if (mat[i][j] > max1) { max2 = max1; // second max = first max max1 = mat[i][j]; // first max = current } // If second max is between current element // and first max else if (mat[i][j] > max2 && mat[i][j] <= max1) { max2 = mat[i][j]; } } } return max1 + max2;} // Driver Code// matrixvar mat = [ [ 1, 2, 3, 4 ], [ 25, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ];document.write(maxSumPair(mat));</script> |
Output
41
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!
