Trace สูงสุดของ sub-matrix ใดๆ ในเมทริกซ์ที่กำหนดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์สองมิติ arr[][] ภารกิจคือการสร้างโปรแกรมเพื่อหา Trace สูงสุดที่เป็นไปได้สำหรับ sub-matrix ใดๆ ของเมทริกซ์ที่กำหนดใน C++

คำอธิบายปัญหา

เราต้องหา trace สูงสุดสำหรับ sub-matrix ใดๆ Trace คือผลรวมของสมาชิกบน diagonal หลักของเมทริกซ์

ตัวอย่างเพื่อเข้าใจปัญหา:

อินพุต

arr[][] = {{-2, 5, 3},
           {1, 6, 2},
           {4, 3, 9}}

เอาต์พุต

15

คำอธิบาย

สำหรับ sub-array:
{1, 6}
{9, 3}

แนวทางแก้ปัญหา

วิธีแก้ง่ายคือหาผลรวมสูงสุดโดยใช้สมาชิกของ diagonal หลักของอาร์เรย์ 2 มิติ Trace กำหนดโดย max subarray sum

ตัวอย่างโค้ด

#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 << "The maximum trace possible for any submatrix is " << CalcMaxTraceSubMat(mat);
    return 0;
}

ผลลัพธ์

The maximum trace possible for any submatrix is 15