# How can this problem be solved in $O(n^{3/2}log(n))$ time?

I can solve the following problem by Jeff Erickson in $$O(n^3)$$(and maybe in $$O(n^2logn)$$) time but how is the $$O(n^{3/2} log(n))$$ time solution possible?

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.

• This is known as the longest increasing subsequence : en.wikipedia.org/wiki/Longest_increasing_subsequence Commented Jul 15, 2023 at 7:12
• There is an optimal subsequence consisting of one or more 1 digit numbers, one or more 2 digit numbers, and so on, and no number is ten times larger than the previous one. Otherwise just drop the last digits of numbers. Commented Jul 15, 2023 at 20:37
• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
Commented Jul 16, 2023 at 4:22

I will assume you know how to solve the problem by keeping a table $$T[i, j]$$ which stores the length of the best solution whose last integer is $$D[i\cdots j] = D[i]D[i+1] \cdots D[j]$$. To compute $$T[i, j]$$ you need to find the best $$T[a, b]$$ such that $$D[a \cdots b] <_{\text{lex}} D[i \cdots j]$$ and $$b < i$$. The computation of $$T[i, j]$$ (provided the previous entries of $$T$$ have been filled) can take $$O(n)$$ if the $$<_{\text{lex}}$$ is implemented in $$O(1)$$ time with a good data structure like a suffix array + LCP; after all, you're always comparing substrings of $$D$$. Naively, this would yield a runtime of $$O(n^3)$$ which is the state at which you seem to be.

Now consider the following observations.

Observation 1: The $$i$$-th term of the optimal sequence should never be longer than the $$i-1$$-th term by more than 1 digit.

Observation 2: Taking $$D[1]$$, $$D[2\cdots3]$$, $$D[4 \cdots 6], \ldots D[n-\sqrt{n} \cdots n]$$ is always a solution, implying that the answer is always at least $$\sqrt{n}$$, and by Observation 1, we get that only the cells of $$T$$ with $$j-i+1 \leq \sqrt{n}$$ should be computed (one can even limit it to $$j-i+1 \leq \sqrt{j}$$, but it doesn't help asymptotically...). There are now $$O(n^{3/2})$$ cells.

Now let's try to speed-up the computation of $$$$T[i, j] = 1 + \max_{a \leq b < i} \Big\{ T[a, b] \; \vert \; D[a\cdots b] <_{\text{lex}} D[i\cdots j] \Big\}.\tag{1}$$$$

As you were already doing in your $$O(n^3)$$ approach, we should only consider $$b - a = j - i$$ or $$b-a = j - i -1$$ (this is just Observation 1). If we keep, for each substring length $$\ell \in \{1, \ldots, \sqrt{n}\}$$ a matrix where $$B[\ell][i] := \max_{b < i} \Big\{ T[b-\ell+1, b]\Big\}$$, then $$B[j-i-1][i]$$ is one candidate for the $$\max$$ in Equation (1), while the other candidate will be

$$\max_{b < i} \Big\{ T[b-j+i+1, b] \; \vert \; D[a\cdots b] <_{\text{lex}} D[i\cdots j] \Big\}.$$

How could we compute this last amount more efficiently? We can assume we're constructing $$T[i, j]$$ in increasing order of $$i$$, and let the length be denoted $$\ell = j-i+1$$. We can keep in memory a set of pairs $$S^{i}_\ell = \Big\{ (T[b-\ell+1, b], D[b-\ell+1 \cdots b]) \; \vert \; b < i\Big\}.$$

If we let $$w = D[i\cdots j]$$, then we're looking for $$\max v \; \text{s.t. } \; (v, y) \in S^i_{\ell} \text{ and } y <_{\text{lex}} w.$$

We're now facing a data structures problem; how can we keep a set of pairs $$(\text{integer}, \text{string of length } \leq \sqrt{n})$$ in a way that quickly allows us to query with a word $$w$$ for the maximum first coordinate whose second coordinate is smaller than $$w$$? It is enough to maintain $$S$$ as a balanced binary search tree, where the ordering of the tree is based solely on the words $$y$$ inserted in it, but every node keeps track of the best value $$v$$ present in its subtree. Notice that because comparisons between strings take $$O(1)$$, searching on the tree will take $$O(\log n)$$. Therefore our entire algorithm runs in $$O(n^{3/2} \log n)$$.