A sequence of integers A$=\backslash \{$a$\_1,$ a$\_2,\backslash$ldots$,$ a$\_$n$\backslash \}$ 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 a$\_1<$ a$\_2>$ a$\_3<$ a$\_4>\backslash$ldots or it follows a$\_1>$ a$\_2<$ a$\_3>$ a$\_4<\backslash$ldots

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 A$=\backslash \{$a$\_1,$ a$\_2,\backslash$ldots$,$ a$\_$n$\backslash \}.$ 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 in Fastest Possible Method.

$1,$ Define the entries of your table in words. Do it in T$($i$)$ or T$($i$,$ j$)$ format

$2.$ State a recurrence for the entries of your table in terms of smaller subproblems.

$3.$ State the base case$($s$).$

$4.$ Write pseudocode for your algorithm to solve this problem.

$5.$ State and analyze the running time of your algorithm in Big O Notation.