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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.