EPIJ 16.11 Pretty printing problem variant 4


The problem stated is to find the longest weakly alternating subsequence. A subsequence is weakly alternating if no three consecutive numbers are increasing or decreasing.

Is it safe to say that the first number in a subsequence is neither increasing or decreasing, and that we start testing for the increasing / decreasing property from the second number in the sequence?

If so, then [1,2,3] would be a valid weakly alternating sequence, but [1,2,3,4] would not.



Never mind. I realize now I was thinking about testing for the increasing / decreasing property as looking backwards from the current index. But we could also look forwards from the current index. Doing so would make it valid to ask about the increasing / decreasing property of the first index in a sequence.