Clean, 211 207 bytes

import StdEnv,Data.List
z=zipWith
$l=maximum[length k-1\\p<-permutations[(v,[x,y])\\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]

Try it online!

A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
The TIO driver takes the same format as the examples through STDIN.

It's too slow to run any of the examples on TIO and probably locally too, but works in theory.

This one does the same thing faster, can do 3x3 or 2x4 on TIO and 4x4 and 3x5 locally.

Clean, 211 207 bytes

import StdEnv,Data.List
z=zipWith
$l=maximum[length k-1\\p<-permutations[(v,[x,y])\\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]

Try it online!

A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
The TIO driver takes the same format as the examples through STDIN.

It's too slow to run any of the examples on TIO and probably locally too, but works in theory.

This one does the same thing faster, can do 3x3 or 2x4 on TIO and 4x4 and 3x5 locally.

Indented:

$ l
    = maximum
        [ length k-1
        \\p <- permutations
            [ (v, [x, y])
            \\y <- [0..] & u <- l
            , x <- [0..] & v <- u
            ]
        , (k, [m: n]) <- map unzip
            (subsequences p)
        | and
            [ all
                ((>) 2 o sum o map abs)
                (zipWith (zipWith (-)) n [m:n])
                :
                zipWith (>) k (tl k)
            ]
        ]

Clean, 211 bytes

import StdEnv,Data.List
z=zipWith
$l=maximum[length k-1\\p<-permutations[(v,[x,y])\\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|prod(map(sum o map abs)(z(z(-))n[m:n]))==1&&and(z(>)k(tl k))]

Try it online!

A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
The TIO driver takes the same format as the examples through STDIN.

It's too slow to run any of the examples on TIO and probably locally too, but works in theory.

This one does the same thing faster, can do 3x3 or 2x4 on TIO and 4x4 and 3x5 locally.

Clean, 211 207 bytes

import StdEnv,Data.List
z=zipWith
$l=maximum[length k-1\\p<-permutations[(v,[x,y])\\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]

Try it online!

A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
The TIO driver takes the same format as the examples through STDIN.

It's too slow to run any of the examples on TIO and probably locally too, but works in theory.

This one does the same thing faster, can do 3x3 or 2x4 on TIO and 4x4 and 3x5 locally.

Clean, 211 bytes

import StdEnv,Data.List
z=zipWith
$l=maximum[length k-1\\p<-permutations[(v,[x,y])\\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|prod(map(sum o map abs)(z(z(-))n[m:n]))==1&&and(z(>)k(tl k))]

Try it online!

A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
The TIO driver takes the same format as the examples through STDIN.

It's too slow to run any of the examples on TIO and probably locally too, but works in theory.

This one does the same thing faster, can do 3x3 or 2x4 on TIO and 4x4 and 3x5 locally.

Clean, 211 bytes

import StdEnv,Data.List
z=zipWith
$l=maximum[length k-1\\p<-permutations[(v,[x,y])\\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|prod(map(sum o map abs)(z(z(-))n[m:n]))==1&&and(z(>)k(tl k))]

Try it online!

A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
The TIO driver takes the same format as the examples through STDIN.

It's too slow to run any of the examples on TIO and probably locally too, but works in theory.

This one does the same thing faster, can do 3x3 or 2x4 on TIO and 4x4 and 3x5 locally.