ค้นหาคู่เฉพาะในเมทริกซ์ใน C++

สมมติว่ามีเมทริกซ์แมทริกซ์ขนาด n x n ของจำนวนเต็ม เราต้องหาค่าสูงสุดของ mat(c, d) - mat(a, b) เหนือตัวเลือกดัชนีทั้งหมด ที่นี่เราต้องจำไว้ว่า c> a และ d> b ดังนั้นหากเมทริกซ์เป็นเหมือน −

ผลลัพธ์จะเป็น 18 เนื่องจาก mat[4, 2] - mat[1, 0] =18 มีความแตกต่างสูงสุด

เพื่อแก้ปัญหานี้ เราจะประมวลผลเมทริกซ์ล่วงหน้าเพื่อให้ดัชนี (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