The precedure of patience sorting is deceptively similar to the RSK algorithm that one might fathom more is true besides the coincidence about the longest increasing subsequence. For instance, I had always believed that the column sizes of the output from both algorithms match. But the following counterexample flew right into my face:
take the permutation to be 134652, then patience sorting gives
1 3 4 6
whereas RSK yields the following standard Young tableau
1 2 4 5
It would be interesting to see the what the second and third rows of SYT correspond to in patience sorting.