2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm pretty sure that the problem statement is not complete. Otherwise why don't you just take operation 3 every time? Maybe does the sub array have to be sorted? $\endgroup$ – Jakube Apr 19 at 7:14
  • $\begingroup$ And at last we want the sub array to be the longest one that can be created with the conditions above and sorted. $\endgroup$ – Bryce Kille Apr 19 at 7:16
  • $\begingroup$ (When trying to interpret, I arrive at we want the sub array to be … one that can be created … and sorted. - can't every array of values with an order be "sorted"? There's a typo in the title.) In the example, why not insert 3 "in the start"? $\endgroup$ – greybeard Apr 19 at 7:49
  • $\begingroup$ I think you have to go in order. I.e. you start from the beginning and either prepend, append or skip. "skip the number in the original array and go to the next" $\endgroup$ – Bryce Kille Apr 19 at 8:04
  • 1
    $\begingroup$ 10,2,7,4,3,13 gives 3,4,7,10,13 as the only maximum valid subarrary $\endgroup$ – Bryce Kille Apr 19 at 8:25
1
$\begingroup$

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.)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.