matrix is a grid of integers with m rows and n columns. A path starts on any cell and moves one step at a time to a cell directly above, below, left or right of the current one. It may not step diagonally, and it may not leave the grid or wrap around from one edge to the opposite one.
A path is increasing when every cell on it holds a value strictly greater than the cell before it, so two equal neighbours can never be consecutive. Return the number of cells on the longest increasing path in matrix. A single cell is a path of length 1.
Start on the 1 in the second column, step down to 4, left to 5, up to 6 and 7, then right along the top row to 8 and 9: seven cells, each larger than the last.
Every neighbour is equal, and equal is not increasing, so no path gets past its first cell.
Reading right to left, 4, 6, 8 is increasing. 2, 9 and 4, 9 only reach two cells.
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2³¹ - 1Ask, for each cell, how long the longest increasing path starting there is. That number depends only on the cell's strictly larger neighbours and never changes, so once a cell's answer is known it never has to be worked out again.
7