16.12 - Longest Alternating Subsequence


This a variant question in Chapter 16 - Dynamic Programming, EPI for Python version.

I am having some issues in reconstruct the longest alternating subsequence. It is doable in O(2^n) time complexity but I am trying to optimize this. The latest version I have is close but off by 1 or 2 elements. Can anyone give me some hints?