หาคู่ดัชนีในเมทริกซ์ให้ผลต่างสูงสุด (c>a, d>b) ใน C++

โจทย์

ให้เมทริกซ์ n x n ต้องการหาค่าสูงสุดของ mat[c][d] - mat[a][b] โดยที่ c > a และ d > b

ตัวอย่าง: เมทริกซ์ 5x5 ผลลัพธ์คือ 18 (จาก mat[4][2] - mat[1][0] = 10 - (-8) = 18)

วิธีแก้ปัญหา (Preprocessing)

สร้างเมทริกซ์ arr_max ที่ arr_max[i][j] เก็บค่าสูงสุดในบริเวณ (i,j) ถึง (n-1,n-1) โดย:

1. เติมมุมขวาล่างและขอบขวา/ล่างก่อน
2. เติมส่วนกลางจากขวาล่างไปซ้ายบน
3. ระหว่างเติม คำนวณผลต่าง arr_max[i+1][j+1] - matrix[i][j] และอัปเดตค่าสูงสุด

ตัวอย่างโค้ด C++

#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