Tích lớn nhất 4 phần tử liền kề trong ma trận C++

Cho ma trận vuông. Tìm tích lớn nhất của 4 phần tử liền kề theo 8 hướng: ngang, dọc, 2 đường chéo.

Thuật toán

• Duyệt mọi ô (i,j) làm ô cuối của nhóm 4.
• Kiểm tra 4 hướng: trái, lên, chéo chính, chéo phụ (nếu đủ 4 ô).
• Tính tích, cập nhật max.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;
const int n = 5;

int FindMaxProduct(int arr[][n], int n) {
    int max = 0, result;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j-3 >= 0) { // ngang trái
                result = arr[i][j] * arr[i][j-1] * arr[i][j-2] * arr[i][j-3];
                if (max < result) max = result;
            }
            if (i-3 >= 0) { // dọc lên
                result = arr[i][j] * arr[i-1][j] * arr[i-2][j] * arr[i-3][j];
                if (max < result) max = result;
            }
            if (i-3 >= 0 && j-3 >= 0) { // chéo chính
                result = arr[i][j] * arr[i-1][j-1] * arr[i-2][j-2] * arr[i-3][j-3];
                if (max < result) max = result;
            }
            if (i-3 >= 0 && j+3 < n) { // chéo phụ
                result = arr[i][j] * arr[i-1][j+1] * arr[i-2][j+2] * arr[i-3][j+3];
                if (max < result) max = result;
            }
        }
    }
    return max;
}

int main() {
    int arr[][5] = {
        {1,2,3,4,5},
        {6,7,8,9,1},
        {2,3,4,5,6},
        {7,8,9,1,0},
        {9,6,4,2,3}
    };
    cout << FindMaxProduct(arr, n);
    return 0;
}

Đầu ra

3024