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: 8 9 6
Longest ascending or descending sequence: 9 6 (2)

Log

© 2004-17 robson | cc unless stated