Given an array of size n, create a sub array with given conditions using dynamic programming
In other words, the procedure produces two subsequences of the given array such that


the only shared element between the two is their first elements
one of them is non-decreasing.
one of them is non-increasing.


Let the given array be $a[0], a[1], \cdots, a[n-1]$. Here are the subproblems. $DP[i][j][[k]$ is the maximal number of elements in any such two subsequences such that their shared element is $a[i]$, the non-decreasing sequence ends at $a[j]$ and the non-increasing sequence ends at $a[k]$. Here $0\le i$, $i\le j\lt n$ , $i\le k\lt n$ and, unless $i=j=k$, $j\not=k$.

The wanted number is the maximum of all $DP[i][j][k]$.

The base cases are $DP[i][i][i]=1$, where $0\le i\lt n$.

What is the recurrence relation? $DP[i][j][k]$ is, basically, the larger of the following two numbers.


the maximum of $DP[i][\ell][k] + 1$ for all $\ell$ such that $i\le\ell\lt j$, $a[\ell]\le a[j]$.
the maximum of $DP[i][j][\ell] + 1$ for all $\ell$ such that $i\le\ell\lt k$, $a[\ell]\ge a[k]$.


How will we fill the 3-dimensional table $DP[i][j][k]$? Roughly, for a fixed $i$, we will find 


$DP[i][i][i] = 1$, 
then $DP[i][i][i+1]$ and $DP[i][i+1][i]$, 
then $DP[i][i][i+2]$, (not including $DP[i][i+1][i+1]$ since $i+1 = i+1$) and $DP[i][i][i+2]$, 
$\cdots$, 
Finally, $DP[i][n-2][n-1]$ and $DP[i][n-1][n-2]$ (there is no $DP[i][n-1][n-1]$ for $i\not=n-1$ and $DP[n-1][n-1][n-1]=1$ is not helpful.)