(i,j) when moves are restricted to coming from the top or left. While filling dp we track the cell with the global maximum length, then reconstruct the path by stepping to a neighbor with dp == current-1 whose value differs by one.

Method 1 — Dynamic Programming (Bottom-up) with path reconstruction

Intuition

If a valid snake sequence ends at cell (i,j), its previous cell must be either (i-1,j) (from above) or (i,j-1) (from left). So the best length ending at (i,j) is 1 + max(dp[i-1][j], dp[i][j-1]) for those neighbors where abs(mat[neighbor] - mat[i][j]) == 1. Fill dp row-major and track the maximum cell.

Approach

Handle edge cases: if mat is empty return [].
Let m = rows,

Related Tags