Hello. I googled the following problem but didn't find any related article.

problem: You are given a N*M size grid of integers. Initially, you are at the leftmost top cell (1,1). You can either go right or down. There are ^(N+M-2) C _N-1 paths in the grid. What is the Longest Increasing Subsequence's length of all the paths.

let A,
{1 2 4 3 }
{2 1 3 4 }
{1 2 4 5 }

You can go take A[1][1],A[1][2],A[2][3],A[2][4],A[3][4] from the path (1,1) -> (1,2) -> (2,2) -> (2,3) -> (2,4) -> (3,4) .

so the answer is 5.

1<=N,M<=1e3

A[i][j]<=1e9;

NB: Can we print the path under the given constraints?