# 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: 3 3 4 9 4
Longest ascending or descending sequence: 3 4 9 (3)

## Log

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