# 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 10 10
Longest ascending sequence: 7 10 (2)

## Log

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