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?
Add the values in the grid in ascending order.
Lets say you are adding the value $$$x$$$ at position $$$(i,j)$$$ then $$$\text{lis}[i][j]=max(\text{lis}[i'][j']+1)$$$ where $$$i' \leq i$$$ and $$$j'\leq j$$$. These max queries can be done using a 2D Segment Tree.
Probably better to use a persistent segment tree to avoid $$$O( (logN)^2)$$$ time, however, that could not fit ML.
Hey, do you think you can elaborate on ur solution a bit? What does it mean when you say "Add the values in the grid in ascending order". What does this mean?
Let $$$\text{lis}[i][j]$$$ be the LIS ending at position $$$(i,j)$$$. Then to calculate $$$\text{lis}[i][j]$$$ such that $$$a[i][j]=x$$$, we need to query all $$$(i',j')$$$ such that $$$i'\leq i$$$ and $$$j'\leq j$$$ and $$$a[i'][j'] \lt x$$$.
So we can find answers for $$$(i,j)$$$ by first finding LIS ending at some value $$$x' \lt x$$$ and doing range max queries on a 2D segment tree.