Subscribe to the weekly news from TrueShelf

## Longest increasing digital subsequence

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.