Maximum value of a[c][d] − a[a][b] with c > a and d > b
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
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;}