C++에서 주어진 행렬의 모든 부분행렬에 대해 가능한 최대 추적

이 문제에서는 2차원 배열 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