Counting Longest Alternating Subsequences

Revision en1, by -synx-, 2018-01-13 17:21:26

It is well known that length of Longest Alternating Subsequence can be found in O(n) (Hint: Think graphically).
My question is can we count the number of Longest Alternating Subsequences in a List in O(n).

As an example consider: A[6]=[2 4 1 3 4 2]
where LAS would be 5, and there are 3 such subsequences.

Tags longest, alternating, subsequence


  Rev. Lang. By When Δ Comment
en1 English -synx- 2018-01-13 17:21:26 378 Initial revision (published)