LIS of a Grid path

Правка en1, от Parvej, 2023-02-18 04:15:24

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Parvej 2023-02-18 04:15:24 693 Initial revision (published)