# Robson ▸ Little Red Book ▸ Monotone subsequence

## Chapter 7 - Question 11

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

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

### Solution 1

I used a modified version of my answer for the ascending sequence problem to solve this.

PHP:

`<?` `    // 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);` `    }` `    // show the original sequence` `    echo 'Random sequence of numbers: ' . implode(\$sequence, ' ');` `    // 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 sequences` `        \$cur_run_asc = array();` `        \$cur_run_desc = 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 (is_array(\$cur_run_asc) && \$sequence[\$b] > \$cur_run_asc[count(\$cur_run_asc)-1])` `                    // add this to the current sequence` `                    \$cur_run_asc[] = \$sequence[\$b];` `                else` `                    // if lower, no need to check any more` `                    \$cur_run_asc = NULL;` `                // if the number is lower than the previous number checked` `                // also true for the first number` `                if (is_array(\$cur_run_desc) && (\$sequence[\$b] < \$cur_run_desc[count(\$cur_run_desc)-1] || !count(\$cur_run_desc)))` `                    // add this to the current sequence` `                    \$cur_run_desc[] = \$sequence[\$b];` `                else` `                    // if higher, no need to check any more` `                    \$cur_run_desc = NULL;                    ` `            }` `        }` `        // if the longest sequence generated from this binary number is more than the previous maximum` `        // - ascending` `        if (count(\$cur_run_asc) > count(\$max_run))` `            // make this the current leader` `            \$max_run = \$cur_run_asc;` `        // - descending` `        if (count(\$cur_run_desc) > count(\$max_run))` `            // make this the current leader` `            \$max_run = \$cur_run_desc;            ` `    }` `    // show the longest sequence that can be made` `    echo '<br/>Longest ascending or descending sequence: ' . implode(\$max_run, ' ') . ' (' . count(\$max_run) . ')';` `?>`

Which produces:

Random sequence of numbers: 4 6 10
Longest ascending or descending sequence: 4 6 10 (3)

## Log

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