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.

Methods of finding solution

Let us briefly explain the different procedures to solve a given problem without any problems.

Brute force method

< p>You can apply a brute force method, i.e. initialize the MAX variable with the sum of the first two elements, then iterate through the array and check the checksum of each pair of elements if it is more significant than MAX ) MAX is the new sum value. But this process will take more time, and the time complexity is O((m*n)2).

Efficient method

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.

Example

#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;
}

Output

maximum sum in Matrix : 107

The above code description

• Store elements in a two-dimensional array and initialize MAX1 and MAX2 with the minimum value INT .
• Traverse the matrix.
  • If the current part is more important than MAX1, replace MAX2 with MAX1 and MAX1 with the current element.
  • If the current section is leaner than MAX1 and more meaningful than MAX2, then replace MAX2 with the current element.
• Calculate the result by adding the two MAX1 and MAX2 and print the result.

>

Conclusion

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!