在C ++中的Matrix中查找特定对

假设有一个nxn的整数矩阵。我们必须在所有索引选择上找到mat(c,d)-mat(a,b)的最大值。在这里，我们必须记住c> a和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