Maximum value of a[c][d] − a[a][b] with c > a and d > b

Medium

Problem

In an n × n matrix, return the maximum of mat[c][d] − mat[a][b] over all index choices where c > a and d > b. The second cell must be strictly below and strictly to the right of the first. Aim for O(n²).

Example 1

Input:  [[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]]
Output: 18

mat[4][2] − mat[1][0] = 10 − (−8).

Also asked as: Find a specific pair in matrix

Test cases

Case 1

Input:    [[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]]
Expected: 18

Case 2

Input:    [[1,2],[3,4]]
Expected: 3

Case 3

Input:    [[4,3],[2,1]]
Expected: -3

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Suffix max of the bottom-right submatrix

Time O(n²)Space O(n²)

maxFromBelowRight[i][j] = max over the submatrix below and right of (i,j). Answer = max(maxFromBelowRight[i+1][j+1] − a[i][j]).

function maxDiff(a) {
const n = a.length;
const suf = Array.from({ length: n + 1 }, () => Array(n + 1).fill(-Infinity));
let ans = -Infinity;
for (let i = n - 1; i >= 0; i--)
for (let j = n - 1; j >= 0; j--) {
suf[i][j] = Math.max(a[i][j], suf[i + 1][j], suf[i][j + 1]);
if (i + 1 < n && j + 1 < n) ans = Math.max(ans, suf[i + 1][j + 1] - a[i][j]);
}
return ans;
}