Increasing Digital Subsequence Problem
Hi,
I was going through the Jeff Erikson notes on Dynamic programming and got stuck with one of the questions in the exercise. Here my pasting the complete question :
Let D[1.. n] be an array of digits, each an integer between 0 and 9. An digital subsequence of
D is an 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 an increasing digital subsequence of the first
several digits of :
3 , 1, 4 , 1, 5 , 9, 2, 6 , 5, 3, 5, 8 , 9 , 7, 9, 3, 2 , 3, 8 , 4, 6, 2, 6, 4 , 3, 3, 8, 3 , 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.
Describe and analyze an efficient algorithm to compute the longest increasing digital subsequence of D.
I thought of starting it with LIS restrircing to single digit number and adding 1 to it but how to compare for range of values like comparing for two k digits.
(restricting to single digit):
DS(i) = 1+ max{DS(j)} where j<=9 and A[i]>A[j]
Please help.
Regards
Abhinav