Let $S[1..n]$ be a sequence of integers between $0$ and $9$. A digital subsequence of $S$ is a sequence $D[1..k]$ of integers such that each integer $D[i]$ is the numerical value of a subarray $S[a_i..b_i]$, where $b_i < a_{i+1}$ for every index $i$.

For example, $[14, 15, 2, 5358, 23, 462]$ is a digital subsequence of the array $$ S = [3,\overline{1,4},\overline{1,5},9,\overline{2},6,\overline{5,3,5,8},9,7,9,3,\overline{2,3},8,\overline{4,6,2},7]. $$

A digital sequence $D[1...k]$ is increasing if $D[i] < D[i+1]$ for every index $i$. The length of a digital sequence $D[1...k]$ sequence is $k$, the number of integers.

Describe a fast algorithm to compute the longest increasing digital subsequence of a given sequence $S$.

A few caveats:

For partial credit, assume that the input sequence contains no zeros.
Faster algorithms are worth more points. Solving the problem in polynomial time is not too hard; the real question is which polynomial.
Be careful with the model of computation; you cannot compare arbitrary integers in constant time.

Level:

Undergraduate