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.

Related Content