Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here:

How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience sorting, dynamic programming or with decision trees. How are these used in real life -- maybe to data streams or something?

To remind you, I put in bold the longest increasing sequence

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

As a bonus, is there any way to use the result that a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n? E.g. Our list as length 16, so there should be an increasing sequence of length 5 or decreasing sequence of length 5. In our case 0,2,6,9,11,15.

Also an increasing sequence of length 8 or a decreasing sequence of length 3: in our case 12,10,1.

• For one application of LIS, see this question on Stackoverflow. – Joe Oct 9 '12 at 23:36
• @Joe The problem you're linking to sounds a bit contrived. From like a homework exercise than something that would actually come up in the real world. – Yuval Filmus Oct 10 '12 at 3:48
• @YuvalFilmus fair enough. it's still a related question – Joe Oct 10 '12 at 6:23