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

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.

• 3-dimensional subproblems are unlikely to yield an algorithm with $O(n^4)$ time. Feb 11 at 22:08

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

• You can actually compare two substrings in $O(\log n)$ by preprocessing the original string using a suffix tree. The comparison becomes an LCA operation on the suffix tree, so your algorithm is actually $O(n^3 \log(n))$. Mar 25 at 21:34
• Well said. The exercises also reads "the fastest algorithm I know for this problem runs in $O(n^{3/2}\log n)$ time". If someone asks what could be that fastest algorithm, I could write an answer. Mar 25 at 21:47