CareerCup

we can do it by dynamic programming. here are the steps:
1. create a new 2d array (let say named temp[][]) of same dimension as original. the element temp[i][j] contains the length of the LIS starting at this point.
2. first fill this temp array with 0's.
3. now, start filling this temp array. let say given array's dimension is MxN.

int arr[M][N]; // given array.
int temp[M][N];

for (i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] == 0){
fill(temp,i,j);
}
}
}

here is fill() function.
void fill(int temp[][], int i, int j){
if(i<0 || j< 0 || i>=M || j>=N)
return 0;

if(temp[i][j] != 0)
return temp[i][j];

int left=0,right=0,up=0,down=0;
if(arr[i-1][j] = arr[i][j] +1)
up = fill(temp,i-1,j);
if(arr[i+1][j] = arr[i][j] +1)
down = fill(temp,i+1,j);
if(arr[i][j-1] = arr[i][j-1] +1)
left = fill(temp,i,j-1);
if(arr[i][j+1] = arr[i][j+1] +1)
right = fill(temp,i,j+1);

temp[i][j] = max(up,down,left,right) + 1;
return temp[i][j];
}

thus it will calculate each element of temp array only once.

4. now, find the maximum element in the array. it's value will be the length of LIS.
max_x=0,max_y=0;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] > temp[max_x][max_y]){
max_x = i;
max_y = j;
}
}
}

5. Above will give the length of LIS. now, to find the LIS, we will check it's neighbours whose LIS value difference is 1.

i=max_x, j= max_y ;
printf("%d ",temp[i][j]);
while(temp[i][j] != 1){
if(temp[i-1][j] = temp[i][j] -1){
i = i-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i+1][j] = temp[i][j] -1){
i = i+1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j-1] = temp[i][j] -1){
j = j-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j+1] = temp[i][j] -1){
j = j+1;
printf("%d ",temp[i][j]);
continue;
}

}


time complexity is: O(M.N)

Do a BFS

do u want longest increasing sub sequence in 2d array ??

2 3 4 5
4 5 10 11
20 6 9 12
6 7 8 40
how come the output : 4 5 6 7 8 9 10 11 12
y not 2 4 5 6 7 8 9 10 11 12 40

we can find out the length of the LCS in each row & the last element now last element of LCS of each LCS canbe compared with first element of LCS of next row.....
if difference is unity ....add the length of two sub sequence & go to next row....

Here is one solution (maybe not optimal)
first it picks up smallest element in the matrix, search a longest increasing sub seq starting at this element, mark all the element on the seq using direct[][] and dist_2_end[][]
driect[i][j] means one the longest sub seq, what is the direction of next movement at i,j
dist_2_end[i][j] means the distance between i,j and the end of the longest sub seq


second, pick up the smallest element which is not marked yet, search a longest increasing sub seq starting at this elements, the search can be simplified if we search some element which is already marked. That means the rest of search should follow the longest sub seq starting at this element.
then mark the longest seq and repeat the second step while all the matrix is marked.

def findmin(a,direct):
 sx=-1
 sy=-1
 mini=999999
 for i,a1 in enumerate(a):
  for j,a2 in enumerate(a1):
#    print a2,
    if a2<mini and direct[i][j]==-1:
     sx, sy, mini = (i,j,a2)
#  print
 return (sx, sy)

def findlongpath(sx, sy, a, direct,dist_2_end,offset):
 if direct[sx][sy]>=10:
  return 0,[]
 if direct[sx][sy]>=0:
  return dist_2_end[sx][sy],[]

 maxlen, maxdirect,maxpath= (0,-2, [])
 direct[sx][sy]=10
 for i,oi in enumerate(offset):
  nx,ny =(sx+oi[0], sy+oi[1] )  
  if nx<0 or nx>=len(a) or ny<0 or ny>=len(a):
   continue
# here is for the condition you want to applt yo the sequence
  if a[nx][ny]!=a[sx][sy]+1:
   continue
  pathlen, path = findlongpath(nx,ny, a,direct, dist_2_end, offset)
  if pathlen>maxlen:
   maxlen=pathlen
   maxpath=path[:]
   maxdirect=i

 direct[sx][sy]=-1
 maxpath.append([sx,sy,maxdirect])
 return maxlen+1, maxpath

def setpath(path,pathlen, direct, dist_2_end):
 for p in path:
  sx, sy, d= (p[0], p[1], p[2])
  direct[sx][sy] = d
  dist_2_end[sx][sy] = pathlen
  pathlen-=1

a=[\
[10,10,1 ,23,-4, 5, 6,23, 7],\
[-6,10,12,3 ,-4, 5,-3,10, 7],\
[10,10,-200,23,-4,-200, 6,23,-7],\
[-2, 3,1 ,99,99, 5,32, 0,-7],\
[10, 4,7 ,8,9, 5, 6,-5,-7],\
[3 , 5,6 ,99,99,-5,-3,-5, 7],\
[18,-6,1 ,23,-4,-200, 6,4 , 7],\
[2 ,10,1 ,-2,14, 5,10,10, 7],\
[2 ,10,1 ,23,-4, 5, 2,2 , 7]\
]

N=len(a)
offset=[[1,0],[0,1],[-1,0],[0,-1]]
direct=[[-1 for j in range(N)] for i in range(N)]
dist_2_end=[[0 for j in range(N)] for i in range(N)]
sx,sy = findmin(a, direct)
lx,ly=(-1,-1)
ml,mx,my = (0,-1,-1)
while (lx!=sx or ly!=sy):
 pathlen, path=findlongpath(sx,sy,a,direct,dist_2_end,offset)
 path.reverse()
 if ml<pathlen:
  ml, mx, my=(pathlen, sx, sy)
 setpath(path,pathlen, direct, dist_2_end)
 lx, ly =(sx, sy)
 sx,sy=findmin(a, direct)

sx, sy=(mx, my)
while ml>0:
 d=direct[sx][sy]
 print 'step',ml,':','[',sx, sy,']', a[sx][sy]
 if d<0:
  break
 sx, sy = (sx +offset[d][0], sy+offset[d][1])
 ml-=1

Not Very efficient but i tried wd Dp seems not working,since we need to have information about all four values around a[i][j]..so not getting how to apply dp..
calculate(i,j,a)
{
level=0;
node b;
b->data=a[i][j];
b->level=0;
enqueue(b);
int maximum=0;
while(queue!=empty)
{
node c=dequeue;
if(c->level>maximum)
maximum=c->level;
level=level+1;
if(c->left->data=a[i][j]+1)
enqueue(c->left);
////
similary for enqueue(c->top),c->left,c->bottom)
}
return maximum;
}
int main()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
a=calculate(i,j,a[]);
if(a>max)
max=a;
}
}

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node{
    int row;
    int col;
    int data;
    int length;
};  
int main()
{
    int m,n,max=0;
    cin>>m>>n;
    queue<node*> q;
    vector<vector<int> > v(m,n);
    for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
    cin>>v[i][j];

   for(int i=0;i<m;i++)
   { for(int j=0;j<n;j++)
    {
        
        node* a=new node;
        a->col=j;
        a->row=i;
        a->data=v[i][j];
        a->length=1;
        q.push(a);
        
        while(!q.empty())
        {
            node* b=new node;
            b=q.front();
            q.pop();
            if(b->length>max)
            max=b->length;
            if(b->row+1<m)
            if(v[b->row+1][b->col]==b->data+1)
            {
               // cout<<"down\n";
                node* c=new node;
                c->row=b->row+1;
                c->col=b->col;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            if(b->row-1>=0)
            if(v[b->row-1][b->col]==b->data+1)
            {
                //cout<<"up\n";
                node* c=new node;
                c->row=b->row-1;
                c->col=b->col;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            if(b->col+1<n)
            if(v[b->row][b->col+1]==b->data+1)
            {
                //cout<<"right\n";
                node* c=new node;
                c->row=b->row;
                c->col=b->col+1;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            if(b->col-1>=0)
            if(v[b->row][b->col-1]==b->data+1)
            {
                //cout<<"left\n";
                node* c=new node;
                c->row=b->row;
                c->col=b->col-1;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            
        }    
    }
}        
    cout<<max;
    system("pause");
    return 0;
    
}

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node{
    int row;
    int col;
    int data;
    int length;
};  
int main()
{
    int m,n,max=0;
    cin>>m>>n;
    queue<node*> q;
    vector<vector<int> > v(m,n);
    for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
    cin>>v[i][j];

   for(int i=0;i<m;i++)
   { for(int j=0;j<n;j++)
    {
        
        node* a=new node;
        a->col=j;
        a->row=i;
        a->data=v[i][j];
        a->length=1;
        q.push(a);
        
        while(!q.empty())
        {
            node* b=new node;
            b=q.front();
            q.pop();
            if(b->length>max)
            max=b->length;
            if(b->row+1<m)
            if(v[b->row+1][b->col]==b->data+1)
            {
               // cout<<"down\n";
                node* c=new node;
                c->row=b->row+1;
                c->col=b->col;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            if(b->row-1>=0)
            if(v[b->row-1][b->col]==b->data+1)
            {
                //cout<<"up\n";
                node* c=new node;
                c->row=b->row-1;
                c->col=b->col;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            if(b->col+1<n)
            if(v[b->row][b->col+1]==b->data+1)
            {
                //cout<<"right\n";
                node* c=new node;
                c->row=b->row;
                c->col=b->col+1;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            if(b->col-1>=0)
            if(v[b->row][b->col-1]==b->data+1)
            {
                //cout<<"left\n";
                node* c=new node;
                c->row=b->row;
                c->col=b->col-1;
                c->data=b->data+1;
                c->length=b->length+1;
                q.push(c);
            }    
            
        }    
    }
}        
    cout<<max;
    system("pause");
    return 0;
    
}

1. consider the matrix as a directed graph
2. compute the in-degree of each node
3. dynamic programming.
(1) Init a queue. If Indegree(v) == 0, put v into queue
(2) Pop a node from the queue, update the length and in-degree of its neighbour nodes
(a) length(neighbour) = max(length(node) + 1 , length(neighbour))
(b) indegree(neighbour) --;
(c) if(indegree(neighbour) == 0) put it into queue
Iterate until the queue is empty
4. return the node with max length

complexity: o(n^2)

hope this will work if not let me know thanks
int mask[100][100];
int liMaxLength,x,y;
void ClearMask()
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			{
				mask[i][j]=0;
			}
		}
	}
}
void PrintMask()
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			{
				cout<<" "<<mask[i][j]<<" ";
			}
		}
		cout<<endl;
	}
	cout<<"the count is "<<liMaxLength<<endl;
}
bool SnakeLength(int a[][4],int i,int j,int count)
{
	bool flag=false;
	count++;
	if(i+1<x &&(a[i+1][j]==a[i][j]+1))
	{
		if(SnakeLength(a,i+1,j,count))
		{
			flag=true;
		}
	}
	if(i-1 > -1 &&(a[i-1][j]==a[i][j]+1))
	{
		if(SnakeLength(a,i-1,j,count))
		{
			flag=true;
		}
	}
	if(j+1<y &&(a[i][j+1]==a[i][j]+1))
	{
		if(SnakeLength(a,i,j+1,count))
		{
			flag=true;
		}
	}
	if(j-1 > -1 &&(a[i][j-1]==a[i][j]+1))
	{
		if(SnakeLength(a,i,j-1,count))
		{
			flag=true;
		}
	}
	if(liMaxLength<count)
	{
		ClearMask();
		liMaxLength=count;
		flag=true;
	}
	if(flag)
	{
		mask[i][j]=1;
		return true;
	}
	return false;
}
int main()
{
	int a[4][4]=		{
		2, 3, 4, 5,
		4, 5, 10, 11,
		20, 6, 9, 12,
		6, 7, 8, 40
						};
	x=y=4;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			if(mask[i][j]!=1)
			SnakeLength(a,i,j,0);
			PrintMask();
		cout<<endl<<endl;
		}
	}
	PrintMask();

	return 0;
}

Use recurs ion...

not optimal but works; JAVA

import java.util.ArrayList;


public class snakegame {
	static int array [][]= {{1,3,4,5}, {4,5,10,11}, {20, 8, 9, 12}, {6,7,8,40}};
	static ArrayList <Integer> the_list = new ArrayList<Integer> ();
	static ArrayList <Integer> temp_arr = new ArrayList<Integer> ();
  public static void main (String []args){
	  
	  
	  for (int i = 0; i <array.length; i++){
		  for (int j = 0; j <array.length; j++){
			  add_temp(i, j);
		  }
		  
	  }
	  System.out.println(the_list.toString());
  }
  
  public static void add_temp (int i, int j){
	  int [] indexes = get_seq(i, j);
	  temp_arr.add(array[i][j]);
	  
	  while (indexes[0] != -1){
		 
		  temp_arr.add(array[indexes[0]] [indexes[1]]); 
		  indexes = get_seq(indexes[0], indexes[1]);
	  }

	  if (temp_arr.size() > the_list.size()){
		  the_list.clear();
		  the_list.addAll(temp_arr);
		
	  }
	  temp_arr.clear();

  }
  public static int[] get_seq (int i, int j){
	  int indexes[] = new int [2];
	  int len = array.length;
	  if (j+1 < len && array[i][j] == array[i][j+1]-1){
		  indexes[0] = i;
		  indexes[1] = j+1;
	  }
	  else if (j-1 >= 0 && array[i][j] == array[i][j-1]-1){
		  indexes[0] = i;
		  indexes[1] = j-1;
	  }
	  else if (i-1 >=0 &&array[i][j] == array[i-1][j]-1){
		  indexes[0] = i-1;
		  indexes[1] = j;
	  }
	  else if (i+1 < len && array[i][j] == array[i+1][j]-1){
		  indexes[0] = i+1;
		  indexes[1] = j;
	  }
	  
	  else
		  indexes[0] =-1;
	  
	  
	  return indexes;
  }
}

If there is something wrong, please let me know. Open to test!

import java.util.ArrayList;
import java.util.Stack;

public class LongestIncreasingSequence {
	int M;
	int N;
	Square[][] matrix;
	int[][] tab;

	class Pair {
		int x;
		int y;

		public Pair(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public Pair() {
			// TODO Auto-generated constructor stub
		}
	}

	class Square {
		private int num;
		boolean isVisited;
		Square parent;

		public int getNum() {
			return num;
		}

		public Square(int num) {
			super();
			this.num = num;
			isVisited = false;
			parent = null;
		}

		@Override
		public String toString() {
			return String.valueOf(num);
		}
	}

	public LongestIncreasingSequence(int m, int n) {
		super();
		M = m;
		N = n;
		matrix = new Square[M][N];

		matrix[0][0] = new Square(2);
		matrix[0][1] = new Square(3);
		matrix[0][2] = new Square(4);
		matrix[0][3] = new Square(5);

		matrix[1][0] = new Square(4);
		matrix[1][1] = new Square(5);
		matrix[1][2] = new Square(10);
		matrix[1][3] = new Square(11);

		matrix[2][0] = new Square(20);
		matrix[2][1] = new Square(6);
		matrix[2][2] = new Square(9);
		matrix[2][3] = new Square(12);

		matrix[3][0] = new Square(6);
		matrix[3][1] = new Square(7);
		matrix[3][2] = new Square(8);
		matrix[3][3] = new Square(40);

		tab = new int[M][N];
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				tab[i][j] = -1;
			}
		}
	}

	public void findLongestIncreasingSeq() {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				int max = returnLargestNeighbor(i, j);
				if (max != -1) {
					tab[i][j] = max + 1;
				} else {
					int len = recursiveFind(i, j);
					tab[i][j] = len;
				}
			}
		}
	}

	private int recursiveFind(int i, int j) {
		ArrayList<Pair> allneighbors = getSatisfiedNeighbor(i, j);
		if (allneighbors.size() == 0) {
			return 1;
		}
		int[] lens = { 0, 0, 0, 0 };
		int k = 0;
		for (Pair neighbor : allneighbors) {
			lens[k++] = 1 + recursiveFind(neighbor.x, neighbor.y);
		}
		int max = Integer.MIN_VALUE;
		for (int len : lens) {
			if (len > max) {
				max = len;
			}
		}
		if (max == Integer.MIN_VALUE) {
			matrix[i][j].parent = null;
		} else if (max == lens[0]) {
			// top
			matrix[i][j].parent = matrix[i - 1][j];
		} else if (max == lens[1]) {
			// bottom
			matrix[i][j].parent = matrix[i + 1][j];
		} else if (max == lens[2]) {
			// right
			matrix[i][j].parent = matrix[i][j + 1];
		} else {
			// left
			matrix[i][j].parent = matrix[i][j - 1];
		}
		return max;
	}

	private ArrayList<Pair> getSatisfiedNeighbor(int i, int j) {
		ArrayList<Pair> pairs = new ArrayList<Pair>();
		if (i - 1 >= 0
				&& matrix[i - 1][j].getNum() + 1 == matrix[i][j].getNum()) {
			// top
			pairs.add(new Pair(i - 1, j));
		}
		if (i + 1 < M && matrix[i + 1][j].getNum() + 1 == matrix[i][j].getNum()) {
			// bottom
			pairs.add(new Pair(i + 1, j));
		}
		if (j + 1 < N && matrix[i][j + 1].getNum() + 1 == matrix[i][j].getNum()) {
			// right
			pairs.add(new Pair(i, j + 1));
		}
		if (j - 1 >= 0
				&& matrix[i][j - 1].getNum() + 1 == matrix[i][j].getNum()) {
			// left
			pairs.add(new Pair(i, j - 1));
		}
		return pairs;
	}

	private int returnLargestNeighbor(int i, int j) {
		int max = -1;
		if (i - 1 >= 0) {
			// top
			if (matrix[i][j].getNum() == matrix[i - 1][j].getNum() + 1
					&& tab[i - 1][j] != -1) {
				if (tab[i - 1][j] > max)
					max = tab[i - 1][j];
			}
		}
		if (i + 1 < M) {
			// bottom
			if (matrix[i][j].getNum() == matrix[i + 1][j].getNum() + 1
					&& tab[i + 1][j] != -1) {
				if (tab[i + 1][j] > max)
					max = tab[i + 1][j];
			}
		}
		if (j + 1 < N) {
			// right
			if (matrix[i][j].getNum() == matrix[i][j + 1].getNum() + 1
					&& tab[i][j + 1] != -1) {
				if (tab[i][j + 1] > max)
					max = tab[i][j + 1];
			}
		}
		if (j - 1 >= 0) {
			// left
			if (matrix[i][j].getNum() == matrix[i][j - 1].getNum() + 1
					&& tab[i][j - 1] != -1) {
				if (tab[i][j - 1] > max)
					max = tab[i][j - 1];
			}
		}
		return max;
	}

	public void print() {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(matrix[i][j] + "\t");
			}
			System.out.println();
		}
	}

	public void printTab() {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(tab[i][j] + "\t");
			}
			System.out.println();
		}
	}

	public void output() {
		System.out.println();
		Stack<Square> stack = new Stack<Square>();
		Pair pair = maxLength();
		while (pair != null) {
			stack.push(matrix[pair.x][pair.y]);
			pair = nextSmallNum(pair);
		}
		while (!stack.isEmpty()) {
			Square s = stack.pop();
			System.out.print(s.getNum() + "\t");
		}
		System.out.println();
	}

	private Pair nextSmallNum(Pair pair) {
		if (tab[pair.x][pair.y] == 1) {
			return null;
		}
		Pair newpair = new Pair();
		if (pair.x - 1 >= 0
				&& tab[pair.x - 1][pair.y] + 1 == tab[pair.x][pair.y]) {
			// top
			newpair.x = pair.x - 1;
			newpair.y = pair.y;
		}
		if (pair.x + 1 < M
				&& tab[pair.x + 1][pair.y] + 1 == tab[pair.x][pair.y]) {
			// bottom
			newpair.x = pair.x + 1;
			newpair.y = pair.y;
		}
		if (pair.y + 1 < N
				&& tab[pair.x][pair.y + 1] + 1 == tab[pair.x][pair.y]) {
			// right
			newpair.x = pair.x;
			newpair.y = pair.y + 1;
		}
		if (pair.y - 1 >= 0
				&& tab[pair.x][pair.y - 1] + 1 == tab[pair.x][pair.y]) {
			// left
			newpair.x = pair.x;
			newpair.y = pair.y - 1;
		}
		return newpair;
	}

	private Pair maxLength() {
		Pair pair = new Pair();
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (tab[i][j] > max) {
					max = tab[i][j];
					pair.x = i;
					pair.y = j;
				}
			}
		}
		return pair;
	}

	public static void main(String[] args) {
		LongestIncreasingSequence seqMatrix = new LongestIncreasingSequence(4,
				4);
		seqMatrix.print();
		seqMatrix.findLongestIncreasingSeq();
		System.out.println();
		seqMatrix.printTab();
		seqMatrix.output();
	}

}

#!/usr/bin/python

matrix = [[2, 3, 4, 5],[4, 5, 10, 11],[20, 6, 9, 12],[6, 7, 8, 40]]
m = len(matrix)
n = len(matrix[0])
lis = []
for i in range(m):
    lis.append([0 for x in matrix[0]])

def maxd(i, j):

    if lis[i][j] > 0:
        return lis[i][j]
    flag = False
    (up, down, left, right) = (0, 0, 0, 0)
    if (i < m - 1) and (matrix[i][j] == matrix[i+1][j] - 1):
        down = maxd(i+1, j)
        flag = True
    if (j < n - 1) and (matrix[i][j] == matrix[i][j+1] - 1):
        right = maxd(i, j+1)
        flag = True
    if (i > 0) and (matrix[i][j] == matrix[i-1][j] - 1):
        up = maxd(i-1, j)
        flag = True
    if (j > 0) and (matrix[i][j] == matrix[i][j-1] - 1):
        left = maxd(i, j-1)
        flag = True
    if not flag:
        return 0
    else:
        lis[i][j] = max(up, down, left, right) + 1
        return lis[i][j]


def getLIS(k, i, j):
    c = str(matrix[i][j])
    if k == 1:
        return c
    if (i < m - 1) and (lis[i][j] == lis[i+1][j] + 1):
        return c + ' ' + getLIS(k-1, i+1, j)
    if (j < n - 1) and (lis[i][j] == lis[i][j+1] + 1):
        return c + ' ' + getLIS(k-1, i, j+1)
    if (i > 0) and (lis[i][j] == lis[i-1][j] + 1):
        return c + ' ' + getLIS(k-1, i-1, j)
    if (j > 0) and (lis[i][j] == lis[i][j-1] + 1):
        return c + ' ' + getLIS(k-1, i, j-1)


def solve(matrix):
    print lis
    for i in range(m):
        for j in range(n):
            if lis[i][j] == 0:
                maxd(i, j)
    print lis
    (maxv, maxi, maxj) = (0, 0, 0);
    for i in range(m):
        for j in range(n):
            if maxv < lis[i][j]:
                maxv = lis[i][j]
                maxi = i
                maxj = j
    print getLIS(maxv, maxi, maxj)

    
solve(matrix)

Simple recursion will do it

public class longest_subsequence
{	
	static ArrayList<ArrayList<Integer>> res;
	static boolean[][] visited;
	static int ROW, COL;
	static int max;
	public static void find(int[][] arr)
	{
		res = new ArrayList<ArrayList<Integer>>();
		ROW = arr.length;
		if(ROW==0) return;
		COL = arr[0].length;
		visited = new boolean[ROW][COL];
		max = 0;
		for(int row= 0;row<ROW;row++)
	  		for(int col=0;col<COL;col++)
	  			if(!visited[row][col])
	  			DFS(arr,row,col,new ArrayList<Integer>());
		
		for(ArrayList<Integer> ls: res)
			System.out.println(ls);
	}
	public static void DFS(int[][] arr, int row, int col, ArrayList<Integer> ans)
	{	
		visited[row][col]=true;
		ans.add(arr[row][col]);
		if(ans.size()>= max)
		{
			if(ans.size()>max) res.clear();
			res.add(new ArrayList<Integer> (ans));
			max = ans.size();
		}
		int cur = arr[row][col];
		if(row>0 && cur-arr[row-1][col] ==-1 )
			DFS(arr,row-1,col,ans);

		if(col>0 && cur-arr[row][col-1] ==-1 )
			DFS(arr,row,col-1,ans);

		if(row<ROW-1 && cur-arr[row+1][col] ==-1)
			DFS(arr,row+1,col,ans);
			
		if(col<COL-1 && cur-arr[row][col+1] ==-1 )
			DFS(arr,row,col+1,ans);
	
		ans.remove(ans.size()-1);
	}
	public static void main(String[] args)
	{
		int[][] arr = {
						{2,3,4,5},
						{4,5,10,11},
						{20,6,9,12},
						{6,7,8,40}
					  };

 		find(arr);
	}
}

public static int findGridLIS(int A[][]){
		int len = A.length;
		int dp [][] = new int [len][len];
		int max =0;
		//intialize memoizing array with all ones

		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++){
				int tempmax = fillDP(A,dp,i,j)+1;
				if(tempmax > max)
					max = tempmax;
			}
		}
		return max;

	}

	public static int fillDP(int [][]A,int[][]dp,int i,int j){
		int len = A.length;
		if(i <0 || j < 0 || i >= len || j >= len ){
			return 0;
		}
		if(dp[i][j] != 0)
			return dp[i][j];
		int left=0,right=0,topLeft=0,topRight=0,bottom=0,top=0,bottomLeft=0,bottomRight=0;
		if(j-1 >= 0&& A[i][j] < A[i][j-1])
			left = fillDP(A,dp,i,j-1);
	
		if(j+1<len && A[i][j] < A[i][j+1])
			right = fillDP(A,dp,i,j+1);
	
		if(i+1 <len && A[i][j] < A[i+1][j])
			bottom = fillDP(A,dp,i+1,j);
	
		if(i-1 >=0 && A[i][j] < A[i-1][j])
			top = fillDP(A,dp,i-1,j);
	
		if(i+1 < len && j-1 >=0 && A[i][j] < A[i+1][j-1])
			bottomLeft = fillDP(A,dp,i+1,j-1);

		if(i+1 >len && j+1 >len && A[i][j] < A[i+1][j+1])
			bottomRight = fillDP(A,dp,i+1,j+1);
	
		if(i-1 >=0 && j-1 >=0 && A[i][j] < A[i-1][j-1])
			topLeft = fillDP(A,dp,i-1,j-1);

		if(i-1 >=0 && j+1 <len && A[i][j] < A[i-1][j+1])
			topRight = fillDP(A,dp,i-1,j+1);
	
		dp[i][j]= Math.max(Math.max(Math.max(top,bottom),Math.max(right,left)),Math.max(Math.max(bottomRight,bottomLeft),Math.max(topLeft,topRight))) +1;
		return dp[i][j]; 

	}

POJ1088

poj.org/problem?id=1088

(chinese). DFS with memoization.

int helper(int row, int col, vector<vector<int>> &grid, vector<vector<int>> &memo) {
	if (memo[row][col] != 0) return memo[row][col];
	// at least one step is possible, since the sequence can be 
	// only one element.
	int up(0), down(0), left(0), right(0);
	if (row > 0 && grid[row - 1][col] == grid[row][col] + 1) 
		up = helper(row - 1, col, grid, memo);
	if (row < grid.size() - 1 && grid[row + 1][col] == grid[row][col] + 1)
		down = helper(row + 1, col, grid, memo);
	if (col > 0 && grid[row][col - 1] == grid[row][col] + 1)
		left = helper(row, col - 1, grid, memo);
	if (col < grid[0].size() - 1 && grid[row][col + 1] == grid[row][col] + 1)
		right = helper(row, col + 1, grid, memo);
	memo[row][col] = max(max(up, down), max(left, right)) + 1;
	return memo[row][col];
}

The above code will only output the length of longest LIS from current coordinate. To get the full sequence, check full code at:

ideone.com/s4ILPd

We could just make the 2D array into a 1D array and find LIS.