Matrix: Find pair with maximum sum in the matrix.

Problem Statement:

You are given a matrix arr[n][n]. You need to find the sum of pair with max sum.

Example

Input : mat[N][M] = {{1, 2, 3, 4},
                 {25, 3, 5, 1},
                 {8, 9, 3, 9},
                 {3, 10, 5, 16}}
Output : 41
Pair (25, 16) has the maximum sum

Solution

Method 1:

We can traverse the matrix 2 times, first time we find the max element and second time we find the 2nd max element and return their sum.

Method 2:

In this approach, we find first and 2nd max element in a single traversal.

1. Initialize 2 variables.
2. Start traversing the array:
a. If the current element in array is greater than the first, then update accordingly.

b. If the current element is in between first and second, then update second to store the value of current variable as second.

3. Return the sum of both.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>

using namespace std;

#define N 4 


int get_max_sum_pair(int mat[N][N]) 
{ 
    int max1 = INT_MIN; 
    int max2 = INT_MIN; 
  
    for (int i = 0; i < N; i++) 
    { 
        for (int j = 0; j < N; j++) 
        { 
            if (mat[i][j] > max1) 
            { 
                max2 = max1;
                max1 = mat[i][j]; 
            } 

            else if (mat[i][j] > max2 && mat[i][j] <= max1) 
            { 
                max2 = mat[i][j]; 
            } 
        } 
    } 
  
    return max1 + max2; 
} 
  
int main() 
{ 
  
    int mat[N][N] = { { 1, 2, 3, 4 }, 
                      { 5, 6, 7, 8 }, 
                      { 9, 10, 11, 12 }, 
                      { 13, 14, 15, 16 } }; 
  
    cout << "The max sum is = "<<get_max_sum_pair(mat) << endl; 
  
    return 0; 
} 

Output:

The max sum is = 31