# Robson » Little Red Book » Ascending subsequence

## Chapter 7 - Question 7

Given a sequence of positive integers, find the longest ascending subsequence. That is, moving from the beginning to end, select from the sequence, while maintaining order, a sequence that is strictly ascending.

For example, if the sequence is 4 7 3 8 21 21 9 0 2 5 6 then 4 7 8 12 21 is the longest subsequence.

### Solution 1

`<?`
`    // generate a string of random numbers`
`    \$max = 1;`
`    for (\$n = 0; \$n < mt_rand(3, 5); \$n++)`
`    {`
`        // add a random number`
`        \$sequence[] = mt_rand(1, 10);`
`    }`
`    // loop through all binary numbers,`
`    // until the length of the binary sequence is longer than the original sequence`
`    for (\$a = 1; \$a < pow(2, count(\$sequence)); \$a++)`
`    {`
`        // make a complete sequence, with leading zeros`
`        // 001, 010, 011, etc`
`        \$binary = str_repeat('0', count(\$sequence)-strlen(decbin(\$a))) . decbin(\$a);`
`        // reset sequence`
`        \$cur_run = array();`
`        // loop through each digit in the binary sequence`
`        for (\$b = 0; \$b < strlen(\$binary); \$b++)`
`        {`
`            // check on`
`            if (\$binary[\$b])`
`                // if the number is higher than the previous number checked`
`                // also true for the first number`
`                if (\$sequence[\$b] > \$cur_run[count(\$cur_run)-1])`
`                    // add this to the current sequence`
`                    \$cur_run[] = \$sequence[\$b];`
`                else`
`                    // if lower, no need to check any more`
`                    break;`
`        }`
`        // if the longest sequence generated from this binary number is more than the previous maximum`
`        if (count(\$cur_run) > count(\$max_run))`
`            // make this the current leader`
`            \$max_run = \$cur_run;`
`    }`
`    // show the original sequence`
`    echo 'Random sequence of numbers: ' . implode(\$sequence, ' ') . '<br/>';`
`    // show the longest sequence that can be made`
`    echo 'Longest ascending sequence: ' . implode(\$max_run, ' ') . ' (' . count(\$max_run) . ')';`
` `
`?>`

Which produces:

Random sequence of numbers: 7 9 6 5 3
Longest ascending sequence: 7 9 (2)

## Log

• November 4, 2006 - Added solution 1.
© 2004-19 robson | cc unless stated