php中求最长递增子序列有两种主流方法：一是o(n²)动态规划，定义dp[i]为以i结尾的lis长度；二是o(n log n)二分优化法，维护tail数组并用二分查找更新。
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 < $n; $i++) { for ($j = 0; $j < $i; $j++) { if ($nums[$j] < $nums[$i]) { $dp[$i] = max($dp[$i], $dp[$j] + 1); } } } return max($dp); } // 测试 $arr = [10, 9, 2, 5, 3, 7, 101, 18]; echo lengthOfLIS($arr); // 输出：4（对应 [2,3,7,18] 或 [2,5,7,101]）
方法二：二分查找优化（O(n log n)，推荐用于大数组）
维护一个辅助数组 tails，其中 tails[i] 存储长度为 i+1 的所有递增子序列中结尾最小的那个值。每次用二分查找定位插入位置，替换或追加元素。
立即学习“PHP免费学习笔记（深入）”；
该方法只返回长度，不直接给出子序列内容；如需还原路径，需额外记录前驱索引。
示例代码：
function lengthOfLISOptimized($nums) { if (empty($nums)) return 0; $tails = []; foreach ($nums as $num) { $left = 0; $right = count($tails); // 二分查找第一个 >= $num 的位置 while ($left < $right) { $mid = (int)(($left + $right) / 2); if ($tails[$mid] < $num) { $left = $mid + 1; } else { $right = $mid; } } $tails[$left] = $num; } return count($tails); } // 测试 $arr = [10, 9, 2, 5, 3, 7, 101, 18]; echo lengthOfLISOptimized($arr); // 输出：4
补充：获取实际的最长递增子序列（非仅长度）
若需返回具体子序列（如 [2, 3, 7, 18]），可在 DP 方法基础上增加 prev 数组记录路径：
- 在 DP 循环中，当
$dp[$j] + 1 > $dp[$i]时，同时记录$prev[$i] = $j - 找到最大值对应索引后，反向追溯
$prev构建结果数组 - 最后用
array_reverse()得到正序子序列
注意事项
- “递增”默认指严格递增（
），如需非严格（<code>），只需修改比较条件 - 输入为空数组或单元素时，函数应正确返回 0 或 1
- PHP 数组索引从 0 开始，注意边界处理，避免 undefined index 警告