C++の行列の各行の要素の最大合計

この問題では、2つの行列mat[][]が与えられます。私たちのタスクは、C++のマトリックスの各行から要素の最大合計を見つけるプログラムを作成することです。

問題の説明

ここでは、現在の行の要素が合計と見なされる最後の行の要素よりも大きくなるように、行列の各行から1つの要素を取得することにより、最大の合計を求めます。上記の条件に従う要素の最大合計を見つけ、それが不可能な場合は-1を出力します。

問題を理解するために例を見てみましょう

入力

mat[][] = {{4, 6, 1},
{2, 5, 7},
{9, 1, 2}}

出力

22

説明

1st row = 6
2nd row = 7
3rd row = 9
Sum = 6 + 7 + 9 = 22

ソリューションアプローチ

簡単な解決策は、行列の最後の行から開始することです。ここで最大数を見つけてMaxSumに追加し、1行上に移動して、その下の行の最大要素よりも小さい最大数を見つけます。一番上の行に到達するまでこれを行います。最大数よりも小さい数が見つからない場合は、-1を返します。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
# define row 3
# define col 3

int RowMaxSum(int a[row][col]){
   int maxValLastRow = 10000;
   int maxSum = 0;
   for (int i = row - 1; i >= 0; i--){
      int maxNo = -1;
      for (int j = 0; j < col; j++)
         if (maxValLastRow > a[i][j] && a[i][j] > maxNo)
            maxNo = a[i][j];
      if (maxNo == -1)
         return -1;
      maxValLastRow = maxNo;
      maxSum += maxValLastRow;
   }
   return maxSum;
}
int main(){
   int a[3][3] = {{4, 6, 1},
                  {2, 5, 7},
                  {9, 1, 2}};
   cout<<"The maximum sum of elements from each row in the matrix is "<<RowMaxSum(a);
   return 0;
}

出力

The maximum sum of elements from each row in the matrix is 22