Home >Backend Development >C++ >Algorithm for finding the pair with maximum sum in a matrix written in C++
In this article, we will discuss finding the pair with maximum sum in a given matrix or 2D array. For example
Input : matrix[m][n] = { { 3, 5, 2 }, { 2, 6, 47 }, { 1, 64, 66 } } Output : 130 Explanation : maximum sum is 130 from element pair 64 and 66. Input : matrix[m][n] = { { 55, 22, 46 }, { 6, 2, 1 }, { 3, 24, 52 } } Output : 107 Explanation : maximum sum is 130 from element pair 55 and 52.
Let us briefly explain the different procedures to solve a given problem without any problems.
You can use an efficient method, that is, initialize two-set the variables MAX1 and MAX2 to 0, and then traverse the two-dimensional array; check whether the current element is greater than MAX1 important. If so, replace MAX2 with MAX1 and MAX1 with the existing part. In this way, we can find the two largest numbers. Obviously, the sum of the two integers is the largest.
#include <bits/stdc++.h> using namespace std; int main() { int m = 3, n = 3; // initialising matrix with values int matrix[m][n] = { { 55, 22, 46 }, { 6, 2, 1 }, { 3, 24, 52 } }; // initialising MAX1 and MAX2 to keep two maximum numbers. int MAX1 = INT_MIN; int MAX2 = INT_MIN; int result; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // check if the element is greater than MAX1. if (matrix[i][j] > MAX1) { MAX2 = MAX1; MAX1 = matrix[i][j]; } // check if the current element is between MAX1 and MAX2. else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) { MAX2 = matrix[i][j]; } } } // calculating maximum sum by adding both maximum numbers. result = MAX1 + MAX2; cout << "maximum sum in Matrix : " << result ; return 0; }
maximum sum in Matrix : 107
In this article, we discussed finding the pair with maximum sum in a given matrix. We discussed ways to find a solution and also discussed the C code for the same. We can write this code in any other language like Java, C, Python, etc. We hope this article was helpful to you.
The above is the detailed content of Algorithm for finding the pair with maximum sum in a matrix written in C++. For more information, please follow other related articles on the PHP Chinese website!