Longest increasing subsequence: Difference between revisions
Content added Content deleted
(added php) |
|||
Line 432: | Line 432: | ||
<pre>2 4 5 |
<pre>2 4 5 |
||
0 2 6 9 11 15</pre> |
0 2 6 9 11 15</pre> |
||
=={{header|PHP}}== |
|||
Patience sorting |
|||
<lang php><?php |
|||
class Node { |
|||
public $val; |
|||
public $back = NULL; |
|||
} |
|||
function lis($n) { |
|||
$pileTops = array(); |
|||
// sort into piles |
|||
foreach ($n as $x) { |
|||
// binary search |
|||
$low = 0; $high = count($pileTops)-1; |
|||
while ($low <= $high) { |
|||
$mid = (int)(($low + $high) / 2); |
|||
if ($pileTops[$mid]->val >= $x) |
|||
$high = $mid - 1; |
|||
else |
|||
$low = $mid + 1; |
|||
} |
|||
$i = $low; |
|||
$node = new Node(); |
|||
$node->val = $x; |
|||
if ($i != 0) |
|||
$node->back = $pileTops[$i-1]; |
|||
if ($i != count($pileTops)) |
|||
$pileTops[$i] = $node; |
|||
else |
|||
$pileTops[] = $node; |
|||
} |
|||
$result = array(); |
|||
for ($node = count($pileTops) ? $pileTops[count($pileTops)-1] : NULL; |
|||
$node != NULL; $node = $node->back) |
|||
$result[] = $node->val; |
|||
return array_reverse($result); |
|||
} |
|||
print_r(lis(array(3, 2, 6, 4, 5, 1))); |
|||
print_r(lis(array(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))); |
|||
?></lang> |
|||
{{out}} |
|||
<pre>Array |
|||
( |
|||
[0] => 2 |
|||
[1] => 4 |
|||
[2] => 5 |
|||
) |
|||
Array |
|||
( |
|||
[0] => 0 |
|||
[1] => 2 |
|||
[2] => 6 |
|||
[3] => 9 |
|||
[4] => 11 |
|||
[5] => 15 |
|||
)</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |