Dấu vết tối đa có thể cho bất kỳ ma trận con nào của ma trận đã cho trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng hai chiều arr [] []. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Dấu vết tối đa có thể cho bất kỳ ma trận con nào của ma trận đã cho trong C ++.

Mô tả vấn đề

chúng ta cần tìm dấu vết tối đa cho bất kỳ ma trận con nào. Dấu vết là tổng các phần tử của đường chéo chính của ma trận.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

15

Giải thích

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản là tìm tổng lớn nhất bằng cách sử dụng phần tử của đường chéo chính của mảng 2-D. Dấu vết được cung cấp bởi tổng của mảng con tối đa.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

The maximum trace possible for any submatrix is 15