# [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!][TIO-jqh3uz1s]

[Clean]: https://github.com/Ourous/curated-clean-linux
[TIO-jqh3uz1s]: https://tio.run/##dVBNi9swED3Hv2JIlyCBFZIte1nshYXtIRDYwhZ6cHzQxpNERJJda5wv9rfXHdndUylCGs28N@@NtLWofe/qqrMIThvfG9fULcEbVd/8KX3RpOdrEyi55TfT/DR0SO5s7vTFuM4VFv2eDnBUy82myVSDretIk6l9KMQpLS7ptZSbzTVTxWI@L2ddpmx6@cxOmerKVBzTwj36UmbK6QY6zz4idO8Bf3XotxigkR9NW1eCYQYc1BCJ@j1IceOlpPSjgszz5WymfcXVJ3kUZOEoZdm/keYnnZPJFxDWeAwpnCXk0KKunq1dx9IIDygj0Ws8qF55YsudsYQtCJE9SZhOJZdCYw3BFDgZ@mQyyeFuvCef/3gNhG6@ek1/4IWSfx2Hgf7OgydtV6@wR4qEiH8MapDnbJlMWF4UZSRHpKYDtmcTkAHWaTHQf9419EWhx0gaBPol3MNX3ve/tzur96FXq3X/cvXame2YfLeadnXrenXoHxYLjoGj@wM "Clean – 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.](https://tio.run/##dZBNa@MwEIbP0a8YsqVIYIW03VyCVVjoHgKBFlrYg22KNlYSgSSr1jhf5LfXlZzNaelFo5l35nlHWhklXW@bujMKrNSu19Y3LcIr1r/dLnuSKCdLHZCcxEn7Pxq35MYIKw/adra4RqPcBrdgy1LnXDuNAT4yK@bF@9xVOUepTQB9lq6mJ/rILDhWlSX9yDzLuZUeOhfp1KvWdihRNy4UdJcVh@xYsbI85ryYTibVbZdzkx2u2S7nXcXOvm1qGiE0dBYaSDj5N7DodKKcMU/RgGeMCXFX9a8o4@v2ZPQDqNFOhQz2DAS0Sta/jFmm0kUe1Kgk9OXAZuEwOqy1QdUCpfkjg/GYxVLwRiOMISbDHCMjATeXO7l@6TGgspPFc/amDkj@dxwW@reP2kmzeIaNwtSQ9PNAAyGiJRlFPC2q1JyUBreq3eugohA5rQr4zbuGuQSap6YB0N/BPTyQB/gJM3IPM5h9rtZGbkLPF8v@6eik1atL8mIkrpvW9nzbz6bTGEOM9gs)