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.
<? // 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: 6 3 8
Longest ascending sequence: 3 8 (2)