Truy vết (trace) lớn nhất của ma trận con trong C++

Cho mảng hai chiều arr[][]. Tìm truy vết lớn nhất của bất kỳ ma trận con nào. Truy vết là tổng các phần tử trên đường chéo chính.

Ví dụ

Đầu vào: arr[][] = {{-2, 5, 3}, {1, 6, 2}, {4, 3, 9}}

Đầu ra: 15

Giải thích

Ma trận con: {1, 6}, {9, 3} (đường chéo: 1+3? Wait, cần kiểm tra lại). Thực tế đường chéo của ma trận con 2x2 bắt đầu từ (1,0) là 1 và 3? Hãy xem code.

Phương pháp giải

Tìm tổng lớn nhất dùng các phần tử trên đường chéo chính của mảng 2D. Truy vết là tổng dãy con lớn nhất trên đường chéo.

Ví dụ

#include <iostream>
using namespace std;

#define row 3
#define col 3

int CalcMaxTraceSubMat(int mat[row][col]) {
    int maxtraceSum = 0, r, c, traceSum;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            r = i, c = j, traceSum = 0;
            while (r < row && c < col) {
                traceSum += mat[r][c];
                r++; c++;
                maxtraceSum = max(traceSum, maxtraceSum);
            }
        }
    }
    return maxtraceSum;
}

int main() {
    int mat[row][col] = {
        {-2, 5, 6},
        {1, 6, 2},
        {4, 3, 9}
    };
    cout << "Truy vết lớn nhất của ma trận con: " << CalcMaxTraceSubMat(mat);
    return 0;
}

Đầu ra

Truy vết lớn nhất của ma trận con: 15