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.$2,4,-1,9,0,5,-2.$ On the other hand, the sequence 2,4,7,3,10,5,5$2,4,7,3,10,5,5$ is not bumpy because the differences between the three consecutive elements 2,4,7$2,4,7$ do not alternate. Two 5'" id="MathJax-Element-7-Frame" role="presentation" style="font-size: 121%; position: relative;" tabindex="0">5'$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.

Answer rating: 100% (QA)

To find the length of the longest bumpy subsequence in a given sequence of integers you can use the dynamic programming algorithm provided earlier Her... View the full answer