Compute the maximum length of an increasing digital subsequence given an array of digits

Question

Consider the following exercise from chapter Dynamic Programming in the book Algorithms by Jeff Erickson.

Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital subsequence of $D$ is a sequence of positive integers composed in the usual way from disjoint substrings of $D$. For example, $3, 4, 5, 6, 8, 9, 32, 38, 46, 64, 83, 279$ is a digital subsequence of the first several digits of $\pi$:$$ \underline 3 , 1, \underline 4 , 1, \underline 5 , 9, 2, \underline 6 , 5, 3, 5, \underline 8 , \underline 9 , 7, 9, \underline{3, 2} , 3, 8, \underline{4, 6} , 2, \underline{6, 4} , 3, 3, \underline{8, 3 }, \underline {2, 7, 9}$$ The length of a digital subsequence is the number of integers it contains, not the number of digits; the preceding example has length $12$. As usual, a digital subsequence is increasing if each number is larger than its predecessor.

Describe and analyze an efficient algorithm to compute the longest increasing digital subsequence of $D$. [Hint: Be careful about your computational assumptions. How long does it take to compare two k-digit numbers?]

For full credit, your algorithm should run in $O(n^4)$ time; faster algorithms are worth extra credit. The fastest algorithm I know for this problem runs in $O(n^{3/2}log n)$ time; achieving this bound requires several tricks, both in the design of the algorithm and in its analysis, but nothing outside the scope of this class.

My main question is how I can define my subproblems? I guess we must have an 3D array like: $$DP[i][j][k]$$ but I can't define $DP[i][j][k]$ very well.

Answer 1

Let $\overline{D[i..j]}$ denote the number formed by the digits $D[i..j]$. For example, if $D=(1,5,7,4,8,3)$, then $\overline{D[2..2]}=5$ and $\overline{D[2..4]}=574$.

The subprolems

Let $DP[i][j]$ with $1\le i\le j\le n$ be the maximum length of a digital subsequence of $D$ the last number of which is $\overline{D[i..j]}$.

The recurrence relation is

$$DP[i][j]=1+\max_{\ell<i,\, \overline{D[k..l]}<\overline{D[i..j]}} DP[k][\ell]$$ where the default value of $\max$ is $0$, i.e., if there is no arguments, $\max$ is $0$.

The answer is the maximum of all $DP[i][j]$'s.

Analysis on time-complexity

Since both $i$ and $j$ range from $1$ to at most $n$, there are at most $n^2$ $DP[i][j]$'s (subproblems).

Let us check how much computation is needed to compute one entry $DP[i][j]$.

We need to list all $k,l$ such that $\ell<i$ and $\overline{D[k..l]}<\overline{D[i..j]}$. Compute the actual number of digits in $\overline{D[i..j]}$, i.e., without the leading zeros. let it be $p$.

• For each $gap=0,1,2,\cdots, p-1$, we can let $(k,l)=(s, s+gap)$, where $s=0, 1, \cdots, i-gap-1$. $\overline{D[k..l]}$ is a number of less than $p$ digit, which must be smaller than $\overline{D[i..j]}$.
  There are at most $n$ choices for the gap with at most $n$ possible choices for $s$ for each gap. It takes $O(n^2)$ to list them.
• For each $s=0, 1, \cdots, i-p-1$, we can check whether $\overline{D[s..s+p]}<\overline{D[i,j]}$ in $O(n)$ time by comparing their digits one by one starting from the most significant digit.
  There are at most $n$ choices for $s$. So we can list all $(s,s+p)$'s such that $\overline{D[s..s+gap]}<\overline{D[i,j]}$ in $O(n^2)$ time.

Once we know all possible $(k,l)$'s, it takes $O(n^2)$ time to compute $DP[i][j]$ using the recurrence relation.

Hence it takes $O(n^2)\cdot O(n^2)=O(n^4)$ time to compute all subproblems. It takes $O(n^2)$ to compute the final answer. Hence, it takes $O(n^4)$ time to run the algorithm.