# Maximum Length Snake Sequence

Given a square matrix, print maximum length snake sequence in it. A Snake sequence is defined as a sequence of numbers where each new number, which can only be located to the right or down of the current number, is either plus or minus one.

For example, from a given cell in a matrix, we can either move right (if that number is ± 1) or move down (if that number is ± 1). The goal of the problem is to find the longest path (Snake Sequence) through the matrix keeping in mind we can only move to a new cell whose value is ± 1 with respect to the current cell.

For example, Maximum length Snake sequence for below matrix is 5 – 4 – 5 – 6 – 7 – 8 – 7 – 6 as highlighted below

Please note that multiple maximum length snake sequences can exist in the matrix. For example, 3 – 4 – 5 – 6 – 7 – 8 – 7 – 6 is another maximum length snake sequence in above matrix.

We can use Dynamic Programming to solve this problem. For each matrix cell (i, j), we need to calculate maximum length of a snake (say L[i][j]) which ends in that cell. Recurrence relation for calculating L[i][j] will be –

if (abs(M[i][j] – M[i][j – 1]) == 1)
L[i][j] = max(L[i][j], L[i][j – 1] + 1)

if (abs(M[i][j] – M[i – 1][j]) == 1)
L[i][j] = max(L[i][j], L[i – 1][j] + 1)

Now, the cell having the maximum value will correspond to the tail of the snake and we can easily trace path back to the head of the snake using L[][] matrix.

## C++

Output:

Maximum length Snake sequence : 5 – 4 – 5 – 6 – 7 – 8 – 7 – 6
Length is : 7

## Java

Output:

Maximum length Snake sequence : 5 – 4 – 5 – 6 – 7 – 8 – 7 – 6
Length is : 7

The time complexity of above solution is O(N*N) and auxiliary space used by the program is O(N*N).

Exercise: Extend the solution for a rectangular matrix

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂