Yea,  I guess profiling is a good choice here rather than just assuming, though I suspect List<IntPair> is going to cost a pretty sizeable chunk of memory over a specialized LongList.  (Tangent: why the heck doesn't the J2SE provide IntList, LongList?  We shouldn't have to write them!)

A good thing is, this appears to be fairly isolated to the internals of the MyersDiff class and thus isn't something we need to expose in our public API to consumers.  snake2x(snake) vs. snake.getX() isn't a big difference either way to higher level code built on top of this.