Geek asks and answers

Applications of the longest increasing subsection

How helpful is the LIS ( Longest Increasing Subsequence ) problem to other CS problems? There are several algorithms that use sorting patience, dynamic programming, or decision trees. How are they used in real life - perhaps in data streams or something like that?

To remind you, I highlight a bold long ascending sequence

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

As a bonus, is it possible to use a result that a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n ? For instance. Our list is 16 in length, so there should be an increasing sequence of length 5 or a 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.

+5
source share
1 answer

LIS Diff, Bram Cohen ( BitTorrent), Bazaar.

diff LCS ( ) . , , , , .

, diff:

 void func1() {
     x += 1
+}
+
+void functhreehalves() {
+    x += 1.5
 }

 void func2() {
     x += 2
 }

Patience Diff , , , .

Patience Diff :

 void func1() {
     x += 1
 }

+void functhreehalves() {
+    x += 1.5
+}
+
 void func2() {
     x += 2
 }

:

.

+3

More articles:


All Articles