C++에서 행렬의 각 행에 있는 요소의 최대 합

이 문제에서는 두 개의 행렬 mat[][]가 제공됩니다. 우리의 임무는 C++에서 행렬의 각 행에서 요소의 최대 합을 찾는 프로그램을 만드는 것입니다.

문제 설명

여기서 우리는 현재 행의 요소가 합으로 간주되는 마지막 행 요소보다 크도록 행렬의 각 행에서 하나의 요소를 취하여 최대 합을 찾을 것입니다. 위의 조건을 따르는 요소의 최대 합을 찾고 불가능하면 -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을 반환합니다.

예시

솔루션의 작동을 설명하는 프로그램,

#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