Tìm cặp có tổng lớn nhất trong ma trận bằng C++

Cho ma trận 2D, tìm cặp hai phần tử có tổng lớn nhất. Ví dụ:

Input: matrix = {{3,5,2},{2,6,47},{1,64,66}} Output: 130 (64+66) Input: matrix = {{55,22,46},{6,2,1},{3,24,52}} Output: 107 (55+52)

Cách vét cạn

Kiểm tra mọi cặp → O((M×N)²).

Cách hiệu quả: Tìm 2 số lớn nhất O(M×N)

Duyệt ma trận một lần, giữ MAX1 (lớn nhất) và MAX2 (lớn nhì). Cập nhật khi gặp phần tử lớn hơn. Tổng lớn nhất = MAX1 + MAX2.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m = 3, n = 3;
    int matrix[3][3] = { {55,22,46}, {6,2,1}, {3,24,52} };
    int MAX1 = INT_MIN, MAX2 = INT_MIN;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] > MAX1) {
                MAX2 = MAX1;
                MAX1 = matrix[i][j];
            } else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) {
                MAX2 = matrix[i][j];
            }
        }
    cout << "maximum sum in Matrix : " << MAX1 + MAX2;
    return 0;
}

Kết quả

maximum sum in Matrix : 107

Kết luận

Tìm cặp tổng lớn nhất trong ma trận bằng cách tìm 2 phần tử lớn nhất trong một lần duyệt O(M×N). Code C++ mẫu.