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