educative.io

Longest Alternating Subsequence - Grokking Dynamic Programming Patterns for

Courses
,
#1

A three element sequence (a1, a2, a3) will be an alternating sequence if its elements hold one of the following conditions:

{a1 > a2 < a3 } or { a1 < a2 > a3}.

Based on the above. I am not able to make sense of the first example

Input: {1,2,3,4}Output: 2Explanation: There are many LAS: {1,2}, {3,4}, {1,3}, {1,4}

Kindly clarify if the above really has an alternating sequence

#2

While considering the second condition { a1 < a2 > a3}.
As 1 < 2, we will start counting length, but as we go to 3, the condition ( a2 > a3 ) becomes false, so we stop counting length at 2.
Same goes for {3,4} , {1,3} and {1,4}. As a result we got the maximum length 2.
Thank you for asking the question.