PHP を使用して最長増加サブシーケンス アルゴリズムを作成する方法

function longestIncreasingSubsequence($arr) { $n = count($arr); $dp = array_fill(0, $n, 1); // 初始化 dp 数组，每个元素的初始值都为 1 for ($i = 1; $i < $n; $i++) { for ($j = 0; $j < $i; $j++) { if ($arr[$i] > $arr[$j]) { $dp[$i] = max($dp[$i], $dp[$j] + 1); } } } $maxLength = max($dp); // 最长递增子序列的长度 return $maxLength; } $arr = [2, 4, 3, 5, 1, 7, 6, 9, 8]; $length = longestIncreasingSubsequence($arr); echo "最长递增子序列的长度为：".$length;

function longestIncreasingSubsequence($arr) { $n = count($arr); $dp = array_fill(0, $n, 1); // 初始化 dp 数组，每个元素的初始值都为 1 for ($i = 1; $i < $n; $i++) { for ($j = 0; $j < $i; $j++) { if ($arr[$i] > $arr[$j]) { if ($dp[$j] + 1 > $dp[$i]) { $dp[$i] = $dp[$j] + 1; $prev[$i] = $j; // 记录递增子序列的上一个元素的下标 } } } } $maxLength = max($dp); // 最长递增子序列的长度 // 构建最长递增子序列 $index = array_search($maxLength, $dp); $lis = []; while ($index !== null) { $lis[] = $arr[$index]; $index = $prev[$index] ?? null; } $lis = array_reverse($lis); // 反转子序列，得到递增顺序 return [ 'length' => $maxLength, 'sequence' => $lis ]; } $arr = [2, 4, 3, 5, 1, 7, 6, 9, 8]; $result = longestIncreasingSubsequence($arr); echo "最长递增子序列的长度为：".$result['length']."
"; echo "最长递增子序列为：".implode(', ', $result['sequence']);