3. (14%) Recurrence formula is what it takes to solve a problem with the dynamic programming technique. In this problem we examine the recurrence formulas for two different sequence problems.

• Consider the longest increasing subsequence (LIS) problem. Let $A=a_1,a_2,\ldots,a_n$ be the input sequence of n numbers. For any $0 \le i \le n$, let $T(i)$ denote the maximum length of any increasing subsequence of A that ends at position i.

It is well-known that $T(i)$ can be expressed as the following recurrence formula.

$T(i) = \begin{cases} 0, & \text{if } i=0, \\ \max_{0 \le j < i,\ a_j < a_i}\{T(j)+1\}, & \text{if } 1 \le i \le n, \end{cases}$

where in the formula we define $a_0 := -\infty$ for convenience. The answer to the input sequence is then given by $\max_{1 \le i \le n} T(i)$.

• Next, consider the "Longest Palindrome Bimodal Subsequence Problem", which is defined as follows. Let $A=a_1,a_2,\ldots,a_n$ be a sequence of n numbers. A subsequence $B=b_1,b_2,\ldots,b_m$ of A is called a bimodal subsequence with pivot k, $1 \le k \le m$, if B is an increasing sequence before position k and a decreasing sequence after position k. That is, $b_i < b_{i+1}$ holds for all $1 \le i < k$ and $b_j > b_{j+1}$ holds for all $k \le j < m$. Furthermore, we say that a bimodal sequence $B=b_1,b_2,\ldots,b_m$ with pivot k is a palindrome bimodal sequence if $k=(m+1)/2$.

For any $1 \le i \le n$, let $PV(i)$ denote the maximum length of any palindrome bimodal subsequence of A that pivots at position i. Write down a valid recurrence formula for $PV(i)$, as the format given above for $T(i)$ for the LIS problem. You may define other auxiliary functions necessary to compose the recurrence formula for $PV(i)$. However, make sure you provide a precise and succinct definition.