Tìm giá trị lớn nhất và nhỏ nhất trong ma trận vuông trong C++

Đề bài

Cho ma trận vuông n×n, tìm phần tử lớn nhất và nhỏ nhất.

Thuật toán tối ưu so sánh

Thay vì so sánh từng phần tử với min/max (2 so sánh/phần tử), ta so sánh từng cặp phần tử đối xứng trong hàng (đầu và cuối), sau đó so sánh nhỏ hơn với min, lớn hơn với max → chỉ 3 so sánh cho 2 phần tử, tiết kiệm 25% so sánh.

Ví dụ minh họa (C++)

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

void getMinMax(int matrix[MAX][MAX], int n) {
    int mn = INT_MAX, mx = INT_MIN;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= n/2; ++j) {
            int a = matrix[i][j];
            int b = matrix[i][n - j - 1];
            if (a > b) {
                if (b < mn) mn = b;
                if (a > mx) mx = a;
            } else {
                if (a < mn) mn = a;
                if (b > mx) mx = b;
            }
        }
    }
    cout << "Max = " << mx << ", Min = " << mn << endl;
}

int main() {
    int matrix[MAX][MAX] = {{15,17,19},{5,1,7},{14,5,16}};
    getMinMax(matrix, 3);
    return 0;
}

Kết quả

Max = 19, Min = 1

Lưu ý: Code gốc có lỗi typo (matri, matrixi, marix), đã sửa trong phiên bản này.