# Get count of longest zigzag sub-sequences

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?

• 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? – Yuval Filmus Jun 27 '18 at 14:11

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.