http://www.geeksforgeeks.org/find-maximum-length-snake-sequence/

SnakeSequence.cpp

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

inline int max(int a, int b) {
    return a > b ? a : b;
}

int trunc(int v) {
    if (abs(v) == 1) return abs(v);
    return 0;
}

int longestSnakeSequence(vector<vector<int>> const& grid, int x, int y) {
    if (x == 0 && y == 0) return 1;
    
    if (x == 0) return trunc(grid[0][y-1] - grid[0][y]) + longestSnakeSequence(grid, 0, y-1);
    if (y == 0) return trunc(grid[x-1][0] - grid[x][0]) + longestSnakeSequence(grid,x-1, 0);
    
    int left = trunc(grid[x][y-1] - grid[x][y]) + longestSnakeSequence(grid,x,y-1);
    int up = trunc(grid[x-1][y] - grid[x][y]) + longestSnakeSequence(grid,x-1,y);
    return max(left, up);
}

int longestSnakeSequence2(vector<vector<int>> const& grid, int N, int M) {
    vector<vector<int>> table(N, vector<int>(M));
    table[0][0] = 1;
    
    for (int m = 1; m < M; ++m)
        table[0][m] = trunc(grid[0][m-1] - grid[0][m]) + table[0][m-1];
    for (int n = 1; n < N; ++n)
        table[n][0] = trunc(grid[n-1][0] - grid[n][0]) + table[n-1][0];
    
    for (int n = 1; n < N; ++n) {
        for (int m = 1; m < M; ++m) {
            table[n][m] = max(trunc(grid[n][m-1] - grid[n][m]) + table[n][m-1],
                              trunc(grid[n-1][m] - grid[n][m]) + table[n-1][m]);
        }
    }
    return table[N-1][M-1];
}

int longestSnakeSequence(vector<vector<int>> const& grid) {
    return longestSnakeSequence(grid, grid.size() - 1, grid[0].size() - 1);
}

int longestSnakeSequence2(vector<vector<int>> const& grid) {
    return longestSnakeSequence2(grid, grid.size(), grid[0].size());
}

int main() {
    vector<vector<int>> v{
        {9, 6, 5, 2},
        {8, 7, 6, 5},
        {7, 3, 1, 6},
        {1, 1, 1, 7}
    };
    
    int n = longestSnakeSequence2(v);
    std::cout<<n;
}