==
This algorithm takes $O(nm)$ time and only $O(n)$ space, since to compute a row you just need the previous row.

If you must return the actual sub sequence this doesn't work. You can keep an array of parent pointers, so that for each state $(i, j)$ you know the previous state in the solution. The longest sub sequence corresponds to a path from $(n-1, m-1)$ to $(0, 0)$ on the parent matrix.  This solution takes $O(nm)$ space.

If you must return the actual sub sequence this doesn't work. You can keep an array of parent pointers, so that for each state $(i, j)$ you know the previous state in the solution. The longest sub sequence corresponds to a path from $(n-1, m-1)$ to $(0, 0)$ on the parent matrix. This solution takes $O(nm)$ space.

Let's try to use less memory. We solve the problem once and save every kth row from the $best$ matrix and from the $parent$ matrix.
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image02.png 90%!