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.CF: https://stackoverflow.com/q/12458641/737051
Longest Increasing Subsequence
algorithms;arrays;subsequences