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.
Hi Evang
I 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.