Longest Zigzag Subsequence
exact_matchmediumby GoldRoger
dparray
Description
Given an array of integers, your task is to find the length of the longest zigzag subsequence. A zigzag subsequence is defined as a sequence of numbers where each element alternately increases and decreases. The sequence does not have to be contiguous in the array, but the order must be maintained. Your goal is to implement a function that efficiently computes the length of such a subsequence using dynamic programming.
Input Specification
The input is a list of integers. The list will have at least 1 and at most 10,000 integers. Each integer will be in the range [-10^9, 10^9].
Output Specification
Return a single integer representing the length of the longest zigzag subsequence.
Starter Code
def solve(input):
pass