Tìm cặp chỉ số (a,b),(c,d) hiệu lớn nhất trong ma trận C++

Cho ma trận n×n. Tìm max của mat[c][d] - mat[a][b] với điều kiện c > a và d > b. Ví dụ ma trận 5×5 cho kết quả 18 từ mat[4][2] - mat[1][0].

Tiền xử lý ma trận max

Tạo ma trận maxArr[i][j] = max giá trị trong vùng từ (i,j) đến (n-1,n-1). Duyệt ngược từ góc phải dưới. Cập nhật kết quả khi xét mat[i][j] với maxArr[i+1][j+1].

Ví dụ minh họa

#include <iostream>
#include <algorithm>
#define N 5
using namespace std;

int findMaxValue(int mat[][N]) {
    int maxVal = -1e9;
    int maxArr[N][N];
    
    maxArr[N-1][N-1] = mat[N-1][N-1];
    int mx = mat[N-1][N-1];
    
    for (int j = N-2; j >= 0; j--) {
        mx = max(mx, mat[N-1][j]);
        maxArr[N-1][j] = mx;
    }
    mx = mat[N-1][N-1];
    for (int i = N-2; i >= 0; i--) {
        mx = max(mx, mat[i][N-1]);
        maxArr[i][N-1] = mx;
    }
    
    for (int i = N-2; i >= 0; i--)
        for (int j = N-2; j >= 0; j--) {
            maxVal = max(maxVal, maxArr[i+1][j+1] - mat[i][j]);
            maxArr[i][j] = max({mat[i][j], maxArr[i][j+1], maxArr[i+1][j]});
        }
    return maxVal;
}

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 << "Hieu lon nhat: " << findMaxValue(mat);
    return 0;
}

Kết quả

Hieu lon nhat: 18