C ++中给定矩阵的任何子矩阵可能的最大迹线

在这个问题中，我们得到了一个二维数组arr [] []。我们的任务是创建一个程序，以查找C ++中给定矩阵的任何子矩阵可能的最大跟踪。

问题描述

我们需要找到任何子矩阵的最大迹线。迹线是矩阵主对角线元素的总和。

让我们举个例子来了解这个问题，

输入值

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

输出结果

15

说明

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

解决方法

一个简单的解决方案是使用二维数组主对角线的元素找到最大和。跟踪由最大子数组总和给出。

示例

该程序说明了我们解决方案的工作原理，

#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