Given an array of size n, create a sub array with given conditions using dynamic programming

Question

We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level: 1. skip the number in original array and go to the next 2. insert the number in the start of the sub array 3. insert the number in the end of the sub array.
And at last we want the sub array to be the longest one that can be created with the conditions above and sorted. For example we have A={10,3,13} now we can insert 10 in the beginning, then 3 at the beginning and finally insert 13 in the end. so the size of sub array is 3.

I know that I must solve this using dynamic programming but I do not know how to do it exactly.

Answer 1

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.)