42. Find a Specific Pair in a Matrix

Given an r x c matrix, find the maximum value of mat[c2][d2] - mat[a][b] over all choices of two cells (a,b) and (c2,d2) such that c2 >= a and d2 >= b (the second cell is on or below-and-right of the first). Print that maximum value.

Input: The first line contains r and c, the matrix dimensions. The next r lines each contain c space-separated integers, which may be negative. Output: Print a single integer - the maximum value of mat[c2][d2] - mat[a][b] over all cells with c2 >= a and d2 >= b.

1 <= r, c <= 100

The constraint that the 'later' cell must be at or below-and-right (never above or to the left) is exactly what makes a single backward sweep sufficient to precompute every cell's best future value correctly.

In a grid, find the biggest possible difference between one cell's value and an earlier cell's value, where 'earlier' means at or above-and-left of it. Brute force: Check every possible pair of cells directly (an 'early' cell and a valid 'later' cell below-and-right of it) - this costs O((r*c)²) in the worst case, far too slow for larger grids. Optimised: Precomputing 'the maximum value anywhere below-and-right of this cell' for every cell ONCE (via a single backward scan) lets you instantly look up the best possible 'later' partner for any 'early' cell in O(1), turning a quadratic all-pairs search into two linear scans of the grid.

Build a matrix M where M[i][j] is the maximum value of mat anywhere in the submatrix from (i, j) to the bottom-right corner, computed bottom-up in a single O(r*c) pass via M[i][j] = max(mat[i][j], M[i+1][j], M[i][j+1], M[i+1][j+1]) with out-of-bounds treated as negative infinity. Then, for every candidate first cell (a, b), the best achievable second-cell value with c2 >= a and d2 >= b is exactly M[a][b], so the answer is the maximum over all (a, b) of M[a][b] - mat[a][b]. This finds the answer in a single linear pass to build M plus a single linear pass to combine, with no per-cell scanning. Time: O(r*c) Space: O(r*c)

Precompute, for every row, the suffix maximum of that row (the maximum value from each column to the last column) in O(r*c) total. Then, for every candidate first cell (a, b), scan every row c2 from a to r-1 and use that row's precomputed suffix max starting at column b to get the best value achievable in that row in O(1), taking the best over all scanned rows. This avoids rescanning individual cells within each row but still requires an explicit scan over rows for every starting cell. Time: O(r^2 * c) Space: O(r*c)

For every possible first cell (a, b) and every possible second cell (c2, d2) with c2 >= a and d2 >= b, directly compute mat[c2][d2] - mat[a][b] and track the maximum value seen across all such pairs. This checks the definition exhaustively over all O(r^2*c^2) cell pairs. Time: O(r^2 * c^2) Space: O(1) extra

1. Precompute, for every cell, the maximum value found anywhere at or below-and-right of it (working from the bottom-right corner backward). 2. Scan the grid again from the bottom-right toward the top-left, and at each cell, compute the best possible difference using that cell as the 'early' point and the precomputed maximum (from just below-and-right of it) as the 'later' point. 3. Track the overall best difference found across the whole scan.

Time: O(r * c) - one backward precomputation pass, one forward (or combined) evaluation pass, both linear in the grid's total size. Space: O(r * c), for the precomputed 'max below-and-right' grid (though this can often be computed and consumed in a single combined backward pass, avoiding a fully separate second grid).

r = c = 1 (only one cell exists, so the best difference is 0); the matrix's minimum value sitting at the bottom-right (limiting which pairs are valid); and r = c = 100 (largest, confirming the suffix-max precompute is O(r*c)).

Be ready to explain the precompute-suffix-maximum technique clearly - it's the same 'precompute the best possible future value' idea used in stock-profit problems, just extended from a 1D array to a 2D grid.