1
$\begingroup$

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

$\endgroup$

migrated from cstheory.stackexchange.com Oct 9 '12 at 22:45

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ For one application of LIS, see this question on Stackoverflow. $\endgroup$ – Joe Oct 9 '12 at 23:36
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Oct 10 '12 at 3:48
  • $\begingroup$ @YuvalFilmus fair enough. it's still a related question $\endgroup$ – Joe Oct 10 '12 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.