PHP实现最长递增子序列算法

本文深入解析了在PHP中高效求解最长递增子序列（LIS）的两种核心方法：兼顾直观易懂的O(n²)动态规划方案，以及面向大规模数据、性能更优的O(n log n)二分优化法，并附上可直接运行的完整代码示例；不仅清晰说明了各自的时间复杂度、实现逻辑与适用场景，还贴心补充了如何还原实际子序列的路径追踪技巧，同时强调“递增”默认为严格递增——无论你是算法初学者还是需要落地优化的PHP开发者，都能快速掌握并灵活应用。

PHP 中求最长递增子序列（Longest Increasing Subsequence, LIS）有多种实现方式，核心在于理解动态规划（DP）或二分优化的思路。下面给出两种实用、易懂且可直接运行的方案。

方法一：动态规划（O(n²)，适合中小规模数组）

定义 dp[i] 表示以索引 i 结尾的最长递增子序列长度。遍历每个位置，向前检查所有比它小的元素，更新 dp 值。

示例代码：

function lengthOfLIS($nums) {
    if (empty($nums)) return 0;
    $n = count($nums);
    $dp = array_fill(0, $n, 1); // 每个元素自身构成长度为1的子序列

    for ($i = 1; $i 

方法二：二分查找优化（O(n log n)，推荐用于大数组）

维护一个辅助数组 tails，其中 tails[i] 存储长度为 i+1 的所有递增子序列中结尾最小的那个值。每次用二分查找定位插入位置，替换或追加元素。

该方法只返回长度，不直接给出子序列内容；如需还原路径，需额外记录前驱索引。

示例代码：

function lengthOfLISOptimized($nums) {
    if (empty($nums)) return 0;

    $tails = [];
    foreach ($nums as $num) {
        $left = 0;
        $right = count($tails);

        // 二分查找第一个 >= $num 的位置
        while ($left 

补充：获取实际的最长递增子序列（非仅长度）

若需返回具体子序列（如 [2, 3, 7, 18]），可在 DP 方法基础上增加 prev 数组记录路径：

• 在 DP 循环中，当 $dp[$j] + 1 > $dp[$i] 时，同时记录 $prev[$i] = $j
• 找到最大值对应索引后，反向追溯 $prev 构建结果数组
• 最后用 array_reverse() 得到正序子序列

注意事项

• “递增”默认指严格递增（<），如需非严格（<=），只需修改比较条件
• 输入为空数组或单元素时，函数应正确返回 0 或 1
• PHP 数组索引从 0 开始，注意边界处理，避免 undefined index 警告

今天关于《PHP实现最长递增子序列算法》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！