Tìm một cặp cụ thể trong Ma trận trong C ++

Giả sử có một ma trận n x n các số nguyên. chúng ta phải tìm giá trị lớn nhất của mat (c, d) - mat (a, b) trên tất cả các lựa chọn của chỉ mục. Ở đây chúng ta phải ghi nhớ rằng c> a và d> b. Vì vậy, nếu ma trận giống như -

Đầu ra sẽ là 18. Điều này là do mat [4, 2] - mat [1, 0] =18 có hiệu số tối đa.

Để giải quyết vấn đề này, chúng tôi sẽ xử lý trước ma trận sao cho chỉ mục (i, j) lưu trữ tối đa các phần tử trong ma trận từ (i, j) đến (n ​​- 1, n - 1) và trong quá trình này tiếp tục cập nhật giá trị lớn nhất được tìm thấy cho đến nay . Sau đó, chúng tôi sẽ trả về giá trị tối đa.

Ví dụ

#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);
}

Đầu ra

Maximum Value is 18