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()得到正序子序列
注意事项
- “递增”默认指严格递增（
<），如需非严格（<=），只需修改比较条件 - 输入为空数组或单元素时，函数应正确返回 0 或 1
- PHP 数组索引从 0 开始，注意边界处理，避免 undefined index 警告
