当前位置：首页 > PHP

Php实现最长递增

2026-02-16 14:01:13PHP

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

获取具体子序列

如果需要获取具体的子序列，可以扩展动态规划方法：

Php实现最长递增

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]