1
$\begingroup$

I know how to get longest zigzag sub-sequence and length of it. There are several methods available for that. But some times there are many sub-sequences available which have same length. How to obtain that?

$\endgroup$
  • 3
    $\begingroup$ What is a zigzag sub-sequences? What methods are you aware of? What problem are you trying to solve? What if there are many longest zigzag sub-sequences, too many to list in polynomial time? $\endgroup$ – Yuval Filmus Jun 27 '18 at 14:11
1
$\begingroup$

Extending the well-known dynamic programming algorithm for Longest Common Subsesequence, we have a poly-time algorithm for Longest Zig-zag Subsequence.

When DPing, just also add another parameter: $\mathrm{A}[\mathrm{i}][\mathrm{j}]$ is the length of the longest zig-zag sequence ending at position $i$ and it is increasing when it ends at $i$ if $j = 0$ and otherwise, decreasing when it ends at $i$ if $j = 1$. So, at a position $i$, you scan from $1$ to $i-1$ and update $\mathrm{A}[\mathrm{i}][\mathrm{0}]$ and $\mathrm{A}[\mathrm{i}][\mathrm{1}]$ gradually. Note that you need to make the $\mathrm{j}$-index alternate while updating.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.