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.