### Evang's blog

By Evang, history, 16 months ago,

Hello

For the past few days, I've been trying to solve this problem, but I still cannot come up with a solution that I can prove.

My only current candidate answer is that the longest common zigzag sequence is always in the longest common subsequence, but because there can be multiple longest common subsequences, I don't know which one to choose. Also, I don't even know if the longest common zigzag sequence is part of the longest common subsequence.

Can anyone help me with this problem? I cannot find any good explanations online.

• 0

 » 2 months ago, # | ← Rev. 3 →   +6 Hi EvangI know this is a very old question, but the answer might help others, as I couldn't find any other post or tutorial about this when I googled it.I solved the problem in a way that is not the most efficient, but it worked. It's O(N*M*log^2(N))I used a Fenwick Tree 2D for maximum values. For each pair of equal numbers, I check with the FT the maximum length of a subsequence ending at that index, using maximum that value. In fact, I used 2 trees, one stores the values with greater value, and the other with smaller values (for the zig zag).I leave my solution here. Anyway, if someone can help us with a better solution, that would be great.