Php实现最长递增
PHP实现最长递增子序列
要使用PHP实现最长递增子序列（LIS）算法，可以采用动态规划或二分查找优化的方法。以下是两种实现方式：
动态规划方法
动态规划的时间复杂度为O(n²)，适用于较小规模的数据。
function lengthOfLIS($nums) {
if (empty($nums)) return 0;
$dp = array_fill(0, count($nums), 1);
$max = 1;
for ($i = 1; $i < count($nums); $i++) {
for ($j = 0; $j < $i; $j++) {
if ($nums[$i] > $nums[$j]) {
$dp[$i] = max($dp[$i], $dp[$j] + 1);
}
}
$max = max($max, $dp[$i]);
}
return $max;
}
// 示例用法
$nums = [10, 9, 2, 5, 3, 7, 101, 18];
echo lengthOfLIS($nums); // 输出4二分查找优化方法
二分查找优化的时间复杂度为O(n log n)，适用于较大规模的数据。
function lengthOfLIS($nums) {
$tails = [];
foreach ($nums as $num) {
$left = 0;
$right = count($tails);
while ($left < $right) {
$mid = $left + intval(($right - $left) / 2);
if ($tails[$mid] < $num) {
$left = $mid + 1;
} else {
$right = $mid;
}
}
if ($left == count($tails)) {
$tails[] = $num;
} else {
$tails[$left] = $num;
}
}
return count($tails);
}
// 示例用法
$nums = [10, 9, 2, 5, 3, 7, 101, 18];
echo lengthOfLIS($nums); // 输出4获取具体子序列
如果需要获取具体的子序列，可以扩展动态规划方法：
function getLIS($nums) {
if (empty($nums)) return [];
$dp = array_fill(0, count($nums), 1);
$prev = array_fill(0, count($nums), -1);
$maxIndex = 0;
for ($i = 1; $i < count($nums); $i++) {
for ($j = 0; $j < $i; $j++) {
if ($nums[$i] > $nums[$j] && $dp[$i] < $dp[$j] + 1) {
$dp[$i] = $dp[$j] + 1;
$prev[$i] = $j;
}
}
if ($dp[$i] > $dp[$maxIndex]) {
$maxIndex = $i;
}
}
$lis = [];
while ($maxIndex != -1) {
array_unshift($lis, $nums[$maxIndex]);
$maxIndex = $prev[$maxIndex];
}
return $lis;
}
// 示例用法
$nums = [10, 9, 2, 5, 3, 7, 101, 18];
print_r(getLIS($nums)); // 输出[2, 3, 7, 101]注意事项
动态规划方法易于理解但效率较低，适合小规模数据。二分查找优化方法效率更高，适合大规模数据。获取具体子序列时，需要额外维护一个数组记录前驱节点。
