C++의 Matrix에서 특정 쌍 찾기

정수로 구성된 n x n 행렬 매트가 있다고 가정합니다. 모든 인덱스 선택에 대해 mat(c, d) - mat(a, b)의 최대값을 찾아야 합니다. 여기서 우리는 c> 그리고 d> b를 염두에 두어야 합니다. 따라서 행렬이 다음과 같은 경우 -

출력은 18이 됩니다. 이것은 mat[4, 2] - mat[1, 0] =18의 차이가 최대이기 때문입니다.

이 문제를 해결하기 위해 index(i, j)가 (i, j)에서 (n - 1, n - 1)까지 행렬의 최대 요소를 저장하도록 행렬을 전처리하고 그 과정에서 지금까지 발견된 최대값을 계속 업데이트합니다. . 그런 다음 최대값을 반환합니다.

예

#include<iostream>
#define N 5
using namespace std;
int findMaxValue(int matrix[][N]) {
   int maxValue = -99999;
   int arr_max[N][N];
   arr_max[N-1][N-1] = matrix[N-1][N-1];
   int max_val = matrix[N-1][N-1];
   for (int j = N - 2; j >= 0; j--) {
      if (matrix[N-1][j] > max_val)
      max_val = matrix[N - 1][j];
      arr_max[N-1][j] = max_val;
   }
   max_val = matrix[N - 1][N - 1];
   for (int i = N - 2; i >= 0; i--) {
      if (matrix[i][N - 1] > max_val)
      max_val = matrix[i][N - 1];
      arr_max[i][N - 1] = max_val;
   }
   for (int i = N-2; i >= 0; i--) {
      for (int j = N-2; j >= 0; j--) {
         if (arr_max[i+1][j+1] - matrix[i][j] > maxValue)
         maxValue = arr_max[i + 1][j + 1] - matrix[i][j];
         arr_max[i][j] = max(matrix[i][j],max(arr_max[i][j + 1],arr_max[i + 1][j]) );
      }
   }
   return maxValue;
}
int main() {
   int mat[N][N] = {
      { 1, 2, -1, -4, -20 },
      { -8, -3, 4, 2, 1 },
      { 3, 8, 6, 1, 3 },
      { -4, -1, 1, 7, -6 },
      { 0, -4, 10, -5, 1 }
   };
   cout << "Maximum Value is " << findMaxValue(mat);
}

출력

Maximum Value is 18