-synx-'s blog

By -synx-, history, 9 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • -7
  • Vote: I do not like it  

»
9 months ago, # |
  Vote: I like it -6 Vote: I do not like it

What is LAS?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Longest Alternating Subsequence.
    a1 > a2 < a3.... or
    a1 < a2 > a3....

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

easily find on google