CareerCup

dynamic programming approach:
for each cell we need to keep maximum length of a "snake" which ends in this cell. Corresponding recurrence for calculating value in cell[i][j]:

dp[i][j] = 1; // snake can always be of length 1
   if (abs(grid[i][j - 1] - grid[i][j]) == 1){
      dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1);
   }
   if (abs(grid[i - 1][j] - grid[i][j]) == 1){
      dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1);
   }

The answer would be the maximum of dp[i][j] for all i, j on the grid.
Space/Time complexity O(n*m).
To reconstruct the path we need to additionally store for each cell the coordinates of the parent (the cell which caused the maximum in the code above)

If you build a graph from the grid by removing all the vertices which don't satisfy the conditions mentioned, this is similar to Longest path problem in a graph. The dynamic programming solution mentioned above won't work

import java.util.ArrayList;

public class SnackNumber {

	private static final int[][] board = new int[][] { 
		{ 1, 3, 2, 6, 8 },
		{ -9, 7, 1, -1, 2 }, 
		{ 1, 5, 0, 1, 9 } };

	public static void snackchecker(int grid[][]) {
		int maxlen = 0;
		int endr = 0;
		int endc = 0;
		
		int[][] dp = new int[board.length][board[0].length];

		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				dp[i][j] = 1;
			}
		}

		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (i == 0 && j == 0) {
					continue;
				}
				if (i > 0 && Math.abs(board[i - 1][j] - board[i][j]) == 1) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + 1);
					maxlen = Math.max(maxlen, dp[i][j]);
					endr = i; endc = j;
				}
				if (j > 0 && Math.abs(board[i][j - 1] - board[i][j]) == 1) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + 1);
					maxlen = Math.max(maxlen, dp[i][j]);
					endr = i; endc = j;
				}
			}
		}
		System.out.println("snack length: " + maxlen);
		
		snacktrackback(dp, endr, endc);
	}
	
	public static void snacktrackback( int grid[][], int i, int j ){
		ArrayList<Integer> track = new ArrayList<Integer>();
		track.add(board[i][j]);
		
		while(grid[i][j] != 1){
			
			if(i > 0 && j > 0){
				if(grid[i][j] == grid[i - 1][j] + 1){
					track.add(board[i - 1][j]);
					i--;
				}else if(grid[i][j] == grid[i][j - 1] + 1){
					track.add(board[i][j - 1]);
					j--;
				}
				
			}else if(j == 0){
				if(grid[i][j] == grid[i - 1][j] + 1){
					track.add(board[i - 1][j]);
					i--;
				}
			}else if (i == 0){
				if(grid[i][j] == grid[i][j - 1] + 1){
					track.add(board[i][j - 1]);
					j--;
				}
			}
		}
		
		System.out.println(track);
	}
	

	public static void main(String[] args) {
		snackchecker(board);
	}

}

this is what i did... We can implement using class.. recursion .. is the best way ...

#include <iostream>
#include <vector>
using namespace std;

vector<int> snakeseq(int rows,int columns,int x,int y,vector<int> vec);

int a[3][5] = {{1,2,3,2,5},{1,3,4,3,2},{1,2,1,2,1} };
int main () {
	int rows, columns;
	vector<int> x;
	rows =3;
	columns=5;

	x= snakeseq(rows,columns,0,0,x);
	system ("pause");
	return 0;
}

vector<int> snakeseq(int rows,int columns,int x,int y,vector<int> vec)
{
	vec.push_back(a[x][y]);
	vector<int> first = vec;
	vector<int> second = vec;

	if( rows > x && columns > y)
	{
		if( (a[x][y] == a[x][y+1]+1)  ||  (a[x][y] == a[x][y+1]-1))
		{
			first = snakeseq(rows,columns,x,y+1,vec);
		}
		if( (a[x][y] == a[x+1][y]+1)  || (a[x][y] == a[x+1][y]-1))
		{
			second = snakeseq(rows,columns,x+1,y,vec);
		}
		if(first.size() > second.size())
			return first;
		else
			return second;
	}
	return vec;
}

My solution by DP. Compiled!

public class SnakeSequence {
	private static final int[][] board = new int[][]{
		      {1, 3, 2, 6, 8},
		      {-9, 7, 1, -1, 2},
		      {1, 5, 0, 1, 9}
	};  
	public static void main(String[] args){
		int max = 0;
		int[][] dp = new int[board.length][board[0].length];
		for(int i = 0; i < board.length; i++){
			for(int j = 0; j < board[0].length; j++){
				dp[i][j] = 1;
			}
		}
		for (int i = 0; i < board.length; i++){
			for(int j = 0; j < board[0].length; j++){
				if(i == 0 && j == 0){
					continue;
				}
				if(i > 0 && Math.abs(board[i - 1][j] - board[i][j]) == 1){
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + 1);
					max = Math.max(max,  dp[i][j]);
				}
				if(j > 0 && Math.abs(board[i][j-1] - board[i][j]) == 1){
					dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + 1);
					max = Math.max(max,  dp[i][j]);
				}
				
			}
		}
		System.out.println(max);
	}

}

Aste's solution would do the trick if the direction is limited to right and down.
The question seems to imply that, but when reading carefully, it does not say so exactly. It only requires "adjacent numbers"
It's better to clarify the question first

same as Aste's solution but I am using backtracking to print all the maximum paths.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SnakeSequence
{
    class Program
    {
        static void reconstruct(int maxlength,int curr,int x,int y,int[,] arr,Stack<Tuple<int,int>> s)
        {
            s.Push(new Tuple<int, int>(x , y));
            if (s.Count == maxlength)
            {
                while (s.Count > 0)
                {
                    Console.Write(s.Pop()+" ");
                }
                Console.WriteLine();
                return;
            }
            if (x - 1 >= 0 && Math.Abs(arr[x - 1, y] - arr[x, y]) == 1)
            {
                reconstruct(maxlength, curr - 1, x - 1, y, arr, s);
            }
            else if (y - 1 >= 0 && Math.Abs(arr[x, y - 1] - arr[x, y]) == 1)
            {
                reconstruct(maxlength, curr - 1, x, y - 1, arr, s);
            }
            else
            {
                Tuple<int,int> top=s.Pop();
                arr[top.Item1, top.Item2] = 999;
                top = s.Peek();
                reconstruct(maxlength, curr - 1, top.Item1, top.Item2, arr, s);
            }
        }

        static void Main(string[] args)
        {
            int[,] arr = new int[,] { { 2, 3, 2, 3, 8 }, { -9, 4, 1, -1, 2 }, { 2, 3, 5, 1, 9 } };
            int[,] dyn = new int[arr.GetLength(0), arr.GetLength(1)];
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    dyn[i, j] = 1;
                    
                }
            }
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    int val1 = 1, val2 = 1;
                    if (i-1>=0 && Math.Abs(arr[i, j] - arr[i - 1, j]) == 1)
                    {
                        val1 = dyn[i - 1,j]+1;
                    }
                    if (j - 1 >= 0 && Math.Abs(arr[i, j] - arr[i, j - 1]) == 1)
                    {
                        val2 = dyn[i, j - 1]+1;
                    }
                    dyn[i, j] = Math.Max(val1, val2);
                }
            }
  
            int max = 0;
            int maxx=0,maxy=0;
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    if(dyn[i,j]>max)
                    {
                        max=dyn[i,j];
                        maxx=i;
                        maxy=j;
                    }
                }
            }
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    if (dyn[i, j] == max)
                    {
                        reconstruct(max, 0, i, j, arr, new Stack<Tuple<int, int>>());
                    }
                }
            }
        }
    }
}

using recursive function to check if the right or down one match the rule. If so, keep on. If not, set this direct not available for the check any more at this time, turn back check other direct.
/*
* Snake.cpp
*
* Created on: Dec 7, 2012
* Author: Kevin Li
*/

#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <stack>
#include <malloc.h>
using namespace std;
enum
{
START, DOWN, RIGHT
};
int width = 5, height = 5, length = 1, maxlength = 0;

struct node
{
int value;
int index;
int direct;
node* next;
bool downAvailable;
bool rightAvailable;
};
node* createNode(int value, int index, int direct)
{
node* n = (node*) malloc(sizeof(node));
n->value = value;
n->index = index;
n->direct = direct;
n->downAvailable = true;
n->rightAvailable = true;
return n;
}
int grid[5][5] =
{
{ 0, 0, 1, 0, 1 },
{ 1, 1, 1, 1, 0 },
{ 1, 0, 1, 1, 1 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 1, 0, 1 } };

stack<node*> nodes, nodesBackup;
int getSnake(int subWidth, int subHeight)
{
//find the match one and push it into the stack
if (nodes.empty())
{
node* cur = createNode(grid[subWidth][subHeight], length, START);
nodes.push(cur);

}

if (((subWidth + 1) < width) && (abs(grid[subWidth][subHeight] - grid[subWidth + 1][subHeight]) == 1))
{
node* down = createNode(grid[subWidth + 1][subHeight], length, DOWN);
if (nodes.top()->downAvailable)
{
length++;
if (nodes.top() != NULL)
{
nodes.top()->next = down;
}
nodes.push(down);
getSnake(subWidth + 1, subHeight);
}

}

if (((subHeight + 1) < width) && (abs(grid[subWidth][subHeight] - grid[subWidth][subHeight + 1]) == 1))
{
node* right = createNode(grid[subWidth][subHeight + 1], length, RIGHT);
if (nodes.top()->rightAvailable)
{
length++;
if (nodes.top() != NULL)
{
nodes.top()->next = right;
}
nodes.push(right);
getSnake(subWidth, subHeight + 1);
}

}
// no match nodes available,check the length and pop the current ones. set the way to this node not
//available any more
if (nodes.top() != NULL)
{
if (nodes.top()->direct == DOWN)
{
nodes.top()->downAvailable = false;
nodes.top()->rightAvailable = true;
}
if (nodes.top()->direct == RIGHT)
{
nodes.top()->downAvailable = true;
nodes.top()->rightAvailable = false;
}
}

if (maxlength <= length)
{
maxlength = length;
cout << "The longest snake is: ";
while (!nodes.empty())
{
node* n = nodes.top();
cout << n->value << " ";
nodesBackup.push(n);
nodes.pop();

}
cout << "Maxlength is " << maxlength;
while (!nodesBackup.empty())
{
node* n = nodesBackup.top();
nodes.push(n);
nodesBackup.pop();
}
cout << endl << endl;
}
nodes.pop();
length--;
return maxlength;
}

int main()
{

for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
cout << "starting point " << i << "," << j << endl;
length = 1;
maxlength = getSnake(i, j);
if (maxlength > (5 - i + 5 - j - 1))
{
return 0;
}
}
}

return 0;
}

public class SnakeSequence {
	int M;
	int N;
	int[][] matrix;
	int[][] table;

	public SnakeSequence(int m, int n) {
		super();
		N = n;
		M = m;
		matrix = new int[M][N];
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				matrix[i][j] = (int) (Math.random() * 8);
			}
		}
		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 longestSSDB() {
		// define and initialize table
		table = new int[M][N];
		for (int j = 0; j < N; j++) {
			if (matchNeighbor(0, j)) {
				table[0][j] = table[0][j - 1] + 1;
			} else {
				table[0][j] = 1;
			}
		}
		for (int i = 0; i < M; i++) {
			if (matchNeighbor(i, 0)) {
				table[i][0] = table[i - 1][0] + 1;
			} else {
				table[i][0] = 1;
			}
		}
		// fill table
		for (int i = 1; i < M; i++) {
			for (int j = 1; j < N; j++) {
				if (matchNeighbor(i, j)) {
					table[i][j] = getLargest(table, i, j) + 1;
				} else {
					table[i][j] = 1;
				}
			}
		}

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

	private int getLargest(int[][] table, int i, int j) {
		int max = 1;
		if (i - 1 >= 0) {
			if (Math.abs(matrix[i][j] - matrix[i - 1][j]) == 1 && table[i - 1][j] > max) {
				max = table[i - 1][j];
			}
		}
		if (Math.abs(matrix[i][j] - matrix[i][j - 1]) == 1 && j - 1 >= 0) {
			if (table[i][j - 1] > max) {
				max = table[i][j - 1];
			}
		}
		return max;
	}

	public void printLargestLength() {
		int max = 1;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (table[i][j] > max) {
					max = table[i][j];
				}
			}
		}
		System.out.println("The longest length is " + max);
	}

	private boolean matchNeighbor(int i, int j) {
		if (i - 1 >= 0) {
			if (Math.abs(matrix[i][j] - matrix[i - 1][j]) == 1) {
				return true;
			}
		}
		if (j - 1 >= 0) {
			if (Math.abs(matrix[i][j] - matrix[i][j - 1]) == 1) {
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		SnakeSequence ss = new SnakeSequence(3, 5);
		System.out.println();
		ss.longestSSDB();
		ss.printLargestLength();
	}

}

package epic;

import java.util.Arrays;

// 动态规划就是要一步步写清楚，多用变量
// dynamic programming

// You are given a grid of numbers. A snake sequence is made up of adjacent numbers such that for each number, the
// number on the right or the number below it is +1 or -1 its value. For example,
//
// 1 3 2 6 8
// -9 7 1 -1 2
// 1 5 0 1 9
//
// In this grid, (3, 2, 1, 0, 1) is a snake sequence.
//
// Given a grid, find the longest snake sequences and their lengths (so there can be multiple snake sequences with the
// maximum length).

/**
* @author Pilot
*/
public class LongestSnakeSequence {
public static final int RIGHT = 1;
public static final int BELOW = -1;
public static final int ITSELF = 2;

/**
* @param maxLength
* matrix that stores max length starts from current coordinate
* @param maxFrom
* matrix that stores the next point according to maxLength matrix
* @param matrix
* original matrix
* @param index
* current coordinate
*/
public static void dpLongestSnake(int[][] maxLength, int[][] maxFrom, int[][] matrix, int[] index) {
if (index[0] < 0 || index[1] < 0) {
return;
}
// System.out.print("(" + index[0] + "," + index[1] + ") ");
int rowIndex = index[0];
int columnIndex = index[1];
int tempMaxLength = 1;
int tempMaxFrom = ITSELF;
int currentValue = matrix[rowIndex][columnIndex];
// left or right
if (columnIndex != matrix[0].length - 1) {
// right
int rightValue = matrix[rowIndex][columnIndex + 1];
if ((currentValue - rightValue == 1) || (currentValue - rightValue == -1)) {
// right can make a snake
int rightValueMaxLength = maxLength[rowIndex][columnIndex + 1];
if (rightValueMaxLength + 1 > tempMaxLength) {
// good snake
tempMaxLength = rightValueMaxLength + 1;
tempMaxFrom = RIGHT;
}
}
}
if (rowIndex != matrix.length - 1) {
// below
int belowValue = matrix[rowIndex + 1][columnIndex];
if ((currentValue - belowValue == 1) || (currentValue - belowValue == -1)) {
// below can make a snake
int belowValueMaxLength = maxLength[rowIndex + 1][columnIndex];
if (belowValueMaxLength + 1 > tempMaxLength) {
// good snake
tempMaxLength = belowValueMaxLength + 1;
tempMaxFrom = BELOW;
}
}
}

maxLength[rowIndex][columnIndex] = tempMaxLength;
maxFrom[rowIndex][columnIndex] = tempMaxFrom;
}

/**
* find the longest snake sequence
*
* @param matrix
* original matrix
* @return the longest snake
*/
public static int[] findLongestSnakeSequence(int[][] matrix) {
// initialize
int[][] maxLength = new int[matrix.length][matrix[0].length];
int[][] maxFrom = new int[matrix.length][matrix[0].length];
int[] index = new int[2];
// record the max length
int maxLengthRecord = -1;
// the start coordinate starting according to maxLengthRecord
int[] maxStartIndexRecord = new int[2];
// traverse along diagonal
int diagonalRow = matrix.length - 1;
int diagonalColumn = matrix[0].length - 1;
while (diagonalRow >= 0 || diagonalColumn >= 0) {
for (int j = matrix[0].length - 1; j > diagonalColumn; j--) {
index[0] = diagonalRow;
index[1] = j;
// dp
dpLongestSnake(maxLength, maxFrom, matrix, index);
// compare
if (index[0] >= 0 && index[1] >= 0 && maxLength[index[0]][index[1]] > maxLengthRecord) {
maxLengthRecord = maxLength[index[0]][index[1]];
maxStartIndexRecord[0] = index[0];
maxStartIndexRecord[1] = index[1];
}
}
for (int i = matrix.length - 1; i > diagonalRow; i--) {
index[0] = i;
index[1] = diagonalColumn;
// dp
dpLongestSnake(maxLength, maxFrom, matrix, index);
// compare
if (index[0] >= 0 && index[1] >= 0 && maxLength[index[0]][index[1]] > maxLengthRecord) {
maxLengthRecord = maxLength[index[0]][index[1]];
maxStartIndexRecord[0] = index[0];
maxStartIndexRecord[1] = index[1];
}
}

// along diagonal
if (diagonalRow >= 0 && diagonalColumn >= 0) {
index[0] = diagonalRow;
index[1] = diagonalColumn;
dpLongestSnake(maxLength, maxFrom, matrix, index);
if (maxLength[index[0]][index[1]] > maxLengthRecord) {
maxLengthRecord = maxLength[index[0]][index[1]];
maxStartIndexRecord[0] = index[0];
maxStartIndexRecord[1] = index[1];
}
}

diagonalColumn--;
diagonalRow--;
}

// longest snake
int[] longestSnake = new int[maxLengthRecord];
int rowIndex = maxStartIndexRecord[0];
int columnIndex = maxStartIndexRecord[1];
longestSnake[0] = matrix[rowIndex][columnIndex];
for (int m = 1; m < longestSnake.length; m++) {
if (maxFrom[rowIndex][columnIndex] == RIGHT) {
columnIndex++;
} else if (maxFrom[rowIndex][columnIndex] == BELOW) {
rowIndex++;
}
longestSnake[m] = matrix[rowIndex][columnIndex];
}

// print the maxLength matrix
System.out.println("maxLength matrix:");
for (int j = 0; j < maxLength.length; j++) {
for (int i = 0; i < maxLength[0].length; i++) {
System.out.print(maxLength[j][i] + "\t");
}
System.out.println();
}
return longestSnake;
}

public static void main(String[] args) {
// 1, 3 ,2, 6, 8
// -9 ,7, 1 ,-1 ,2
// 1 ,5, 0, 1, 9
int[][] matrix = { { 1, 3, 2, 6, 8 }, { -9, 7, 1, -1, 2 }, { 1, 5, 0, 1, 9 } };
System.out.println("original matrix:");
for (int j = 0; j < matrix.length; j++) {
for (int i = 0; i < matrix[0].length; i++) {
System.out.print(matrix[j][i] + "\t");
}
System.out.println();
}
int[] result = findLongestSnakeSequence(matrix);
System.out.println("longest snake: " + Arrays.toString(result));
}
}

public class SnakeSequence{
	static int[][]arr ={{1,3,2,6,8},{-9,7,1,-1,2},{1,5,0,1,9}};      
	static boolean bip=true;
    static boolean bis=true;
    static  boolean bjp=true;
    static boolean bjs=true;
	static void snake(int i, int j)
           	{
		        
		        
		        String s = "";
           		if(bip && i < arr.length-1  &&  Math.abs(arr[i][j] - arr[i+1][j]) == 1 )
           		{
           			s =s+arr[i][j];
           			System.out.println(s);
           			 bis=false;
           			 bip=true;
    		         bjp=true;
    		         bjs=true;
           			snake(i+1,j);
           		}
           		if ( bis && Math.abs(arr[i][j] - arr[Math.abs(i-1)][j]) == 1)
           		{
           			s =s+arr[i][j];
           			System.out.println(s);
           			bip=false;
           		    bis=true;
   		            bjp=true;
   		            bjs=true;
           			snake(Math.abs(i-1),j);
           			
           		}
           			if (bjp && j<4  &&  Math.abs(arr[i][j] - arr[i][j+1]) == 1)
           			{
           				s =s+arr[i][j];
               			System.out.println(s);
               		   bjs = false;
               		   bip=true;
   		               bis=true;
   		               bjp=true;
   		         
               		   snake(i,j+1);
           				
           			}
           				if ( bjs && Math.abs(arr[i][j] - arr[i+1][Math.abs(j-1)]) == 1)
           				{
           					s =s+arr[i][j];
                   			System.out.println(s);
                   			bjp =false;
                   			bip=true;
           		            bis=true;
           		            bjs=true;
                   			snake(i,Math.abs(j-1));		
           				}
           				else 
           				{
           					if(i==0&&j==0)
           					{
           						snake(i,j+1);
           					}
           						else 
           						{System.out.println(arr[i][j]);
           							System.exit(0);
           							}		
           				}
           					
           	}
	public static void main(String[] args) throws Exception
	{ 
	    snake(0,0);
	}
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int **makeArr(int N, int M, int inp) {
	int i = 0, j = 0;
	int **arr = (int **)malloc(sizeof(int *)*N);
	
	for(i = 0 ; i < N ; i++) {
		arr[i] = (int *)malloc(sizeof(int)*M);
		if(inp) {
			for(j = 0 ; j < M ; j++) {
				scanf("%d", &arr[i][j]);
			}
		}
		else {
			for(j = 0 ; j < M ; j++) {
				arr[i][j] = 0;
			}
		}
	}
	return arr;
}

int *makeQueue(int N, int M) {
	int *arr = (int *)malloc(sizeof(int)*N*M);
	memset(arr, 0 , sizeof(int)*N*M);
	return arr;
}

void enqueue(int *arr, int v, int *f, int *r) {
	(*r)++;
	arr[*r] = v;
}
int dequeue(int *arr, int *f, int *r) {
	int v = arr[*f];
	arr[*f] = 0;
	(*f)++;
	return v;
}

int diff(int a, int b) {
	return (a-b == -1 || a-b == 1 || a-b == 0);
}
/*

Make a res 2-d array which contains 0/1 to determine whether an index is already been visited or not.
Simple breadth-first search here. 
our data is contained in arr.
value that we enqueue in our queue is index of the element of the array: for (i,j)..we enqueue i*M+j
this function returns the length of the longest snake sequence which is contained in maxlen 
*/
int findLongest(int **arr, int N, int M) {
	int **res = makeArr(N,M,0);
	int f = 0;
	int r = -1;
	int *queue = makeQueue(N, M);
	int i = 0; 
	int j = 0;
	int len = 0;
	int maxlen = 0;
	
	for(i = 0 ; i < N ; ++i) {
		for(j = 0 ; j < M ; ++j) {
			if(!res[i][j]) {
				f = 0;
				r = -1;
				enqueue(queue, i*M+j, &f, &r);
				while(f <= r) {
					int v = dequeue(queue, &f, &r);
					int x = v/M;
					int y = v%M;
					res[x][y] = 1;
					len = len+1;
					
					if(x > 0 && !res[x-1][y] && diff(arr[x-1][y], arr[x][y]))
						enqueue(queue, (x-1)*M+y, &f, &r);
					if(x < N-1 && !res[x+1][y] && diff(arr[x+1][y], arr[x][y]))
						enqueue(queue, (x+1)*M+y, &f, &r);
					if(y > 0 && !res[x][y-1] && diff(arr[x][y-1], arr[x][y]))
						enqueue(queue, x*M+y-1, &f, &r);
					if(y < M-1 && !res[x][y+1] && diff(arr[x][y+1], arr[x][y]))
						enqueue(queue, x*M+y+1, &f, &r);
				}
				if(len > maxlen)
					maxlen = len;
				len = 0;
			}
		}
	}
	return maxlen;
}

/*
  1 3 2  6 8
 -9 7 1 -1 2
  1 5 0  1 9
*/

int main() {
	int N = 3;
	int M = 5;
	int **arr = makeArr(N, M, 1);
	printf("%d\n", findLongest(arr, N, M));
	return 0;
}

I think mine is really easy to understand, Please let know if you find any problem.

//
//  SnakeSequence.cpp
//  
//  Modified by Roger on 03/18/14.
//
//  Program to print Hamiltonian cycle

#include <vector>
#include <iostream>

using namespace std;

int a[3][5] = { { 1,  3, 2,  1,  0 }, 
                { -9, 7, 1, -1, -1 }, 
                { 1,  5, 0,  1, -2 } };


void snakeseq(int rows,int columns,int x,int y,
              vector<int> &vec, vector<int> &snapshot)
{
    vec.push_back(a[x][y]);
    
    if (vec.size() > snapshot.size())
        snapshot = vec;

    if(x < rows && y < columns) {
        if( (a[x][y] == a[x][y+1]+1)  ||  
            (a[x][y] == a[x][y+1]-1))
            snakeseq(rows,columns,x,y+1,vec,snapshot);

        if( (a[x][y] == a[x+1][y]+1)  || 
            (a[x][y] == a[x+1][y]-1))
            snakeseq(rows,columns,x+1,y,vec,snapshot);
    }
    
    vec.pop_back();
}

int main () {
    int rows = 3, columns = 5, max = 0;
    vector<int> vec,snapshot,result;

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < columns; ++j) {
            snakeseq(rows,columns,i,j,vec,snapshot);
            if ((int)snapshot.size() > max)
                result = snapshot;
        }
    }

    for (size_t i = 0; i < result.size(); ++i)
        cout << result[i] << " ";
    cout << endl;

    return 0;
}

import java.util.*;
class snake{
public static int[][] a = new int[][] {{1,3,2,6,8},{-9,7,1,-1,2},{1,5,0,1,9}};
public static ArrayList snakepath = new ArrayList();
public static boolean set = false;
public static void main(String[] args){
snake sn = new snake();
sn.snkpath(a.length,a[0].length,0,0);
for(int i=0;i<snakepath.size()-1;i++){
System.out.print(snakepath.get(i)+",");
}
if(snakepath.size()>=1)
System.out.print(snakepath.get(snakepath.size()-1)+"");
System.out.println("");
}
public void snkpath(int row,int col,int i, int j){
if(row>i && col>j){
if(j+1<col && Math.abs(a[i][j]-a[i][j+1])==1){
snakepath.add(a[i][j]);
set =true;
snkpath(row,col,i,j+1);
}
else if(i+1<row && Math.abs(a[i][j]-a[i+1][j])==1){
snakepath.add(a[i][j]);
set = true;
snkpath(row,col,i+1,j);
}
else if(i+1<row && j+1<col && Math.abs(a[i][j]-a[i+1][j+1])==1){
snakepath.add(a[i][j]);
set = true;
snkpath(row,col,i+1,j+1);
}
else if(i+1>=row && j+1>=col){return;}
else{
if(i+1>=row){if(set == true)snakepath.add(a[i][j]);return;}
j++;
snakepath.clear();
set = false;
snkpath(row,col,i,j);
}
}
}
}

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int a[3][5],b[3][5];

void solve()
    {
    int temp1,temp2;
    
    for(int i=1;i<5;i++)
        {
        if(abs(a[0][i]-a[0][i-1])==1)
        {
            b[0][i]=b[0][i-1]+1;
    }
        
    }
    
    for(int i=1;i<3;i++)
        for(int j=0;j<5;j++)
        {
        if(!j)
            {
            if(abs(a[i][0]-a[i-1][0])==1)
                b[i][0]=abs(b[i-1][0])+1;
            b[i][0]=-1*b[i][0];
        }
        else
            {
            temp1=0;temp2=0;
            if(abs(a[i][j]-a[i][j-1])==1)
               temp1=abs(b[i][j-1]);
            if(abs(a[i][j]-a[i-1][j])==1)
                temp2=abs(b[i-1][j]);
            if(temp1||temp2)
            {
                if(temp1>temp2)
                b[i][j]=temp1+1;
            else
               { b[i][j]=temp2+1;
            b[i][j]=-1*b[i][j];
        }
            }
            
        }
    }
}
    
    
    int main()
    {
    memset(b,0,sizeof(0));
        for(int i=0;i<3;i++)
            for(int j=0;j<5;j++)
            {
            scanf("%d",&a[i][j]);
        }
        solve();
        for(int i=0;i<3;i++)
          {  for(int j=0;j<5;j++)
            {
            printf("%d ",b[i][j]);
        }
           printf("\n");
          }
    return 0;

}

why so many people use DP ?
Can DP find all longest paths?

public class snake_sequence
{	static ArrayList<ArrayList<Integer>> res;
	static int ROW;
	static int COL;
	static int max;
	static boolean[][] visited;
	public static void find(int[][] arr)
	{
		ROW =arr.length;
		if(ROW==0) return;
		COL = arr[0].length;
	 	res = new ArrayList<ArrayList<Integer>>();
	 	max = 0;
	 	visited = new boolean[ROW][COL];
	 	for(int row= 0;row<ROW;row++)
	 	{
	 		for(int col=0;col<COL;col++)
	 			if(!visited[row][col])
	 				DFS(arr,row,col,0,new ArrayList<Integer>());
	 	}

	 	for(ArrayList<Integer> ls : res)
	 		System.out.println(ls);
	}
	private static void DFS(int[][] arr, int row, int col,int l_max,ArrayList<Integer> t_arr)
	{
		t_arr.add(arr[row][col]);
		visited[row][col]=true;
		if(l_max>=max)
		{
			if(l_max>max)
			{
				res.clear();
				max = l_max;
			}
			res.add(new ArrayList<Integer>(t_arr));
		}
		if(col<COL-1 && Math.abs(arr[row][col]-arr[row][col+1]) ==1 )
			DFS(arr,row,col+1,l_max+1,t_arr);

		if(row<ROW-1 && Math.abs(arr[row][col]-arr[row+1][col]) ==1 )
			DFS(arr,row+1,col,l_max+1,t_arr);

		t_arr.remove(t_arr.size()-1);	
 	}
	public static void main(String[] args)
	{
		int[][] arr = {
						{1,3,2,3,4},
						{-9,7,1,-1,3},
						{1,0,0,1,9}
					  };

 		find(arr);
	}
}

DP is definitely what they are looking for here in this question. My interpretation of the DP formula is kinda different. Since the snake only goes to right and down, thus we start the memoization table from the right down corner, and use the memoization table to record how long can the snake go if it starts from here. The DP formula is simple:

steps[i][j] = 1+max(steps[i+1, j], steps[i, j+1])

If i+1 or j+1 is out of bound, disregard that term. If i+1 and j+1 are all out of bound, set the second term in DP formula zero. Don't forget to check number continuity.
Playable code at

ideone.com/s7QdEs

vector<int> helper(vector<vector<int>> grid) {
	if (!grid.size() || !grid[0].size()) return vector<int>();
	int rowCount(grid.size()), colCount(grid[0].size());
	vector<vector<int>> memo(colCount);
	vector<int> ret;
	for (int row = rowCount - 1; row >= 0; --row) {
		for (int col = colCount - 1; col >= 0; --col) {
			vector<int> right, down;
			if (col + 1 < colCount && \
				abs(grid[row][col + 1] - grid[row][col]) == 1)
				right = memo[col + 1];
			if (row + 1 < rowCount && \
				abs(grid[row + 1][col] - grid[row][col]) == 1)
				down = memo[col];
			memo[col] = right.size() > down.size() ? right : down;
			memo[col].push_back(grid[row][col]);
			ret = ret.size() > memo[col].size() ? ret : memo[col];
		}
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

The below method use dp and also use dfs to find all longest paths. The idea is use a table to keep track of the longest path number as well as its parent node. In the end, use that parent node of longest path node to find the longest path with DFS.

input 		{1,3,2,6,8},
                        {-9,7,1,2,2},
                        {1,5,0,1,9}};

output 
1 1 2 1 1 
1 1 3 4 5 
1 1 4 5 1 

32122
32101
32121

import java.util.ArrayList;
import java.util.List;

public class SnakeSequence {
    static int longest = 1;

    private class Node{
        int num;
        int length;
        List<Node> parents;

        public Node(int num, int length, List l){
            this.num = num;
            this.length = length;
            this.parents = l;
        }
    }



    public List<String> getLongestSeq(int[][] mat){
        int rows = mat.length, cols = mat[0].length;
        Node[][] table = new Node[rows][cols];
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                table[i][j] = new Node(mat[i][j], 1, new ArrayList());
            }
        }
        for(int i = 0; i< rows; i++){
            for(int j = 0; j< cols; j++){
                if(j-1>= 0 && Math.abs(mat[i][j-1]-mat[i][j]) <= 1){
                    table[i][j].length = Math.max(table[i][j].length, table[i][j-1].length + 1);
                    table[i][j].parents.add(table[i][j-1]);
                }
                if(i-1 >= 0 && Math.abs(mat[i-1][j] - mat[i][j]) <= 1){
                    if(table[i][j].length == table[i-1][j].length+1){
                        table[i][j].parents.add(table[i-1][j]);
                    }else if( table[i][j].length < table[i-1][j].length + 1){
                        if(table[i][j].parents.size()>0) table[i][j].parents.remove(0);
                        table[i][j].parents.add(table[i-1][j]);
                    }

                    table[i][j].length = Math.max(table[i][j].length,table[i-1][j].length+1);

                }
                longest = Math.max(longest, table[i][j].length);
            }
        }

        List<String> l = findPath(table,longest);
        return l;

    }

    public List<String> findPath(Node[][] table, int longest){
        List<String> l = new ArrayList<>();
        for(int i = 0; i < table.length; i++){
            for(int j = 0; j < table[0].length; j++){
                System.out.print(table[i][j].length + " ");
            }
            System.out.println();
        }
        for(int i = 0; i < table.length; i++){
            for(int j = 0; j < table[0].length; j++){
                if(table[i][j].length == longest){
                    dfs(table[i][j],"",l);
                }
            }
        }
        return l;
    }
    public void dfs(Node n, String s, List<String> l){
        if(n.parents.isEmpty()) l.add(new StringBuilder(s+String.valueOf(n.num)).reverse().toString());
        for( Node node : n.parents){
            dfs(node, s + String.valueOf(n.num),l);
        }
    }

    public static void main(String[] args){
        int[][] mat = { {1,3,2,6,8},
                        {-9,7,1,2,2},
                        {1,5,0,1,9}};
        List<String> l = new SnakeSequence().getLongestSeq(mat);
        for(String s : l){
            System.out.println(s);
        }

    }
}

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


    class SnakePath
    {
    	static List<List<Integer>> allPath = new ArrayList<List<Integer>>();
        public static void reconstruct(int maxlength,int curr,int x,int y,int[][] arr,Stack<Integer> s)
        {
            s.push(arr[x][y]);
            if (s.size() == maxlength)
            {   
            	int e=0;
            	List<Integer> p = new ArrayList<Integer>();
                while (e<s.size())
                {
                	//System.out.print(s.get(s.size()-1-e)+ "  ");
                   	p.add(s.get(s.size()-1-e));
                	e++;
                }
                if(!allPath.contains(p))
                	allPath.add(p);
                //System.out.println();
                return;
            }
            if (x - 1 >= 0 && Math.abs(arr[x - 1][ y] - arr[x][ y]) == 1)
            {
                reconstruct(maxlength, curr - 1, x - 1, y, arr, s);
                s.pop();
            }
            if (y - 1 >= 0 && Math.abs(arr[x][y - 1] - arr[x][ y]) == 1)
            {
                reconstruct(maxlength, curr - 1, x, y - 1, arr, s);
                s.pop();
            }
        }

        public static void main(String[] args)
        {
        	SnakePath v = new SnakePath();
            int[][] arr = { { 1, 3, 2, 6, 8 }, { -1, 0, 1, 0, -1 }, { 0, 5, 0, 1, 5 } };
            int[][] dyn = new int[arr.length][arr[0].length];
            for (int i = 0; i < arr.length; i++)
            {
                for (int j = 0; j < arr[0].length; j++)
                {
                    dyn[i][ j] = 1;
                    
                }
            }
            for (int i = 0; i < arr.length; i++)
            {
                for (int j = 0; j < arr[0].length; j++)
                {
                    if (i-1>=0 && Math.abs(arr[i][ j] - arr[i - 1][ j]) == 1)
                    {
                        dyn[i][j] = Math.max(dyn[i - 1][j]+1,dyn[i][j]);
                    }
                    if (j - 1 >= 0 && Math.abs(arr[i][ j] - arr[i][ j - 1]) == 1)
                    {
                    	dyn[i][j] = Math.max(dyn[i][j-1]+1,dyn[i][j]);
                    }
                }
            }
            
            /*for (int i = 0; i < arr.length; i++)
            {
                for (int j = 0; j < arr[0].length; j++)
                {
                	System.out.print(dyn[i][j]+" ");
                }
                System.out.println();
            }*/
                        
            int max = 0;
            int maxx=0,maxy=0;
            for (int i = 0; i < arr.length; i++)
            {
                for (int j = 0; j < arr[0].length; j++)
                {
                    if(dyn[i][j]>max)
                    {
                        max=dyn[i][j];
                        maxx=i;
                        maxy=j;
                    }
                }
            }
            for (int i = 0; i < arr.length; i++)
            {
                for (int j = 0; j < arr[0].length; j++)
                {
                    if (dyn[i][ j] == max)
                    {
                        v.reconstruct(max, 0, i, j, arr, new Stack<Integer>());
                    }
                }
            }
            
            for(int i=0;i<allPath.size();i++)
            {
            	List<Integer> t = allPath.get(i);
            	for(int j = 0; j<t.size();j++)
            	{
            		System.out.print(t.get(j) + "  ");
            	}
            	System.out.println();
            }
        }
    }

public static void findSeq(int[][] grid, int[] values) {
    	for(int i = 0; i < grid.length; i++) {
    		for (int j = 0; j < grid[0].length; j++) {
				findSeqFromGivenPoint(grid, i, j, values, 0);
			}
    	}
    }
    
    public static void findSeqFromGivenPoint(int[][] grid, int i, int j, int[] values, int level) {
        values[level] = grid[i][j];
        if(i < grid.length && j < grid[0].length) {
            if((j + 1) < grid[0].length && Math.abs(grid[i][j] - grid[i][j + 1]) == 1) {
                findSeqFromGivenPoint(grid, i, j + 1, values, level + 1);
            }
            
            if((i + 1) < grid.length &&  Math.abs(grid[i][j] - grid[i + 1][j]) == 1) {
                findSeqFromGivenPoint(grid, i + 1, j, values, level + 1);
            }
            
            if(level > 0) {
                ArrayList<Integer> finalList = new ArrayList<>();
                for(int k = 0; k <= level; k++) {
                    finalList.add(values[k]);
                }
                
                list.add(finalList);
            }
        }
    }