A sequence of integers is said to be bumpy when the signs of the differences between two consecutive terms in the sequence strictly alternate between $+$ and $-$ values. A difference of zero can never be part of a bumpy sequence. So the sequence either follows or it follows

$.$

An example of a bumpy sequence is $2,4,-1,9,0,5,-2.$ On the other hand, the sequence $2,4,7,3,10,5,5$ is not bumpy because the differences between the three consecutive elements $2,4,7$ do not alternate. Two $5\text{'}$s also show up at the end of the sequence causing the consecutive difference to be zero.

You are given a sequence of integers

$.$ Your task is to find the length of the longest bumpy subsequence in A$.$ Design a dynamic programming algorithm to solve this problem.

Please answer the following parts:

Define the entries of your table in words. E$.$g$.$ T$($i$)$ or T$($i$,$ j$)$ is $...$

State a recurrence for the entries of your table in terms of smaller subproblems. Don't forget your base case$($s$).$

Write pseudocode for your algorithm to solve this problem.

State and analyze the running time of your algorithm.

Faster $($in asymptotic Big O notation$)$ and correct solutions are worth more credit.