การติดตามสูงสุดที่เป็นไปได้สำหรับเมทริกซ์ย่อยใดๆ ของเมทริกซ์ที่กำหนดใน C++

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

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

เราจำเป็นต้องค้นหาการติดตามสูงสุดสำหรับเมทริกซ์ย่อยใดๆ การติดตามเป็นผลรวมขององค์ประกอบของเส้นทแยงมุมหลักของเมทริกซ์

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

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

ผลลัพธ์

15

คำอธิบาย

For the sub-array: {1, 6}
{9, 3}

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

วิธีแก้ปัญหาง่ายๆ คือการหาผลรวมสูงสุดโดยใช้องค์ประกอบของเส้นทแยงมุมหลักของอาร์เรย์ 2 มิติ การติดตามกำหนดโดยผลรวมของอาร์เรย์ย่อยสูงสุด

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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