# Make maximum number of numbers with $n$ digits

Let $$A=[1..n]$$ be an array of $$n$$ decimal digits. $$A[i]$$ contains one number from $$\{0,1,\dots,9\}$$. We can put adjacent elements of $$A$$ beside them to form a number in which, created number should form increasing sequence $$S$$ and we want make $$S$$ as large as possible and for each $$i=1..n$$, $$A[i]$$ appears in at most one number. For example if $$A[1..7]=[1,2,3,9,0,9,8]$$ then

$$S=\langle 1,2,3,9,98\rangle.$$

How a dynamic programming can solve above problem?

• Where did you encounter this problem? Please provide a link to the original web page or credit the original source appropriately. May 1 at 4:55