Longest Alternating Subsequence Problem

Given an array ARR of integers, determine the length of the longest alternating subsequence.

Input:

ARR = {Array elements}

Output:

Length of the longest alternating subsequence

Example:

Input:

ARR = {3, 10, 1, 2, 30}

Output:

4

Explanation:

The longest alternating subsequences could be {3, 10, 1, 30} or {3, 10, 2, 30}.

Constraints:

• 1 <= T <= 5
• 1 <= N <= 5000
• 1 <= ARR[i] <= 10^5

Time limit: 1 second

Note:

A sequence a1, a2, ..., an is alternating if it satisfies either a1 < a2 > a3 < a4 > a5... or a1 > a2 < a3 > a4 < a5....