A zig-zag sequence is a sequence A where, for every index i between 2 and |A| - 1, A[i] is either larger than both of its neighbors A[i - 1] and A[i + 1], or smaller than both. For example, . 1, 3, 2. 5, 4 is a zig-zag sequence, whereas 1, 2, 3. 5. 4 is not (see figure below). in this problem, your goal is find the length of the longest zig-zag subsequence of a given sequence. For example, for the sequence 1, 2, 3, 5, 4, the answer is 3 (corresponding to, e.g., 1, 5, 4). Define a recursive function for computing the length of the longest zig-zag subsequence. Your equation should lead to an efficient (polynomial time) dynamic program, but you do not need to provide the algorithm, a proof of correctness, or the running time. Please remember to give a formal definition for your recursive function(s), and include any base cases