Interesting to see this posted as I'm taking algorithms this semester and the homework due in 2 weeks has a LIS question.

I accidentally implemented the longest common subsequence that runs in linear space[1] and it actually worked as a drop in replacement for LIS, for my particular question.

[1] http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Dyn...