PHP中求最长递减子序列（LDS）本质是动态规划问题，通过取负转为求最长递增子序列（LIS），再用二分优化至O(n log n)；要求严格递减，输出为保持原序的子序列而非连续子数组。
PHP 中求最长递减子序列（Longest Decreasing Subsequence, LDS）本质是动态规划问题，与最长递增子序列（LIS）思路相似，只需将比较逻辑改为“严格递减”（
方法一：动态规划（O(n²) 时间复杂度）
定义 dp[i] 表示以索引 i 结尾的最长递减子序列长度。对每个 i，向前检查所有 j ，若 $arr[j] > $arr[i]（满足递减），则更新 dp[i] = max(dp[i], dp[j] + 1)。
示例代码：
function longestDecreasingSubsequence($arr) {
if (empty($arr)) return [];
$n = count($arr);
$dp = array_fill(0, $n, 1); // 每个元素自身构成长度为1的子序列
$parent = array_fill(0, $n, -1); // 记录路径，用于重构序列
for ($i = 1; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($arr[$j] > $arr[$i] && $dp[$j] + 1 > $dp[$i]) {
$dp[$i] = $dp[$j] + 1;
$parent[$i] = $j;
}
}
}
// 找最大长度及对应末尾位置
$maxLength = max($dp);
$endIndex = array_search($maxLength, $dp);
// 重构子序列（逆序收集）
$result = [];
$curr = $endIndex;
while ($curr != -1) {
array_unshift($result, $arr[$curr]);
$curr = $parent[$curr];
}
return $result;
}
// 测试
$arr = [10, 22, 9, 33, 21, 50, 41, 60, 80, 1];
print_r(longestDecreasingSubsequence($arr)); // 输出类似 [50, 41, 1] 或 [33, 21, 1] 等（取决于相等长度时的选择）
方法二：优化版（O(n log n)，基于二分查找）
适用于只需求长度，或需高效处理大数据。维护一个辅助数组 tail，其中 tail[k] 存储长度为 k+1 的递减子序列的**末尾最大可能值**（注意：这里是“最大”，因为要给更小的数留出插入空间）。遍历时对每个元素，在 tail 中找第一个 ≤ 当前数的位置，替换之；若当前数更小，则追加到末尾。
立即学习“PHP免费学习笔记（深入）”；
关键点：
- 将原数组取负后求 LIS，等价于求 LDS（因 -a b）
- 或直接修改二分逻辑：在递减场景下维护“尾部尽可能大”的单调栈
推荐做法（简洁可靠）：
function longestDecreasingLength($arr) {
if (empty($arr)) return 0;
$negArr = array_map(fn($x) => -$x, $arr); // 取负，转为求 LIS
return longestIncreasingLength($negArr);
}
function longestIncreasingLength($arr) {
$tail = [];
foreach ($arr as $x) {
$left = 0;
$right = count($tail);
while ($left < $right) {
$mid = (int)(($left + $right) / 2);
if ($tail[$mid] < $x) {
$left = $mid + 1;
} else {
$right = $mid;
}
}
if ($left == count($tail)) {
$tail[] = $x;
} else {
$tail[$left] = $x;
}
}
return count($tail);
}
注意事项与常见误区
递减子序列要求严格递减（即不能有相等元素），若需允许非严格递减（≥），需将条件改为 $arr[j] >= $arr[i] 并同步调整二分查找逻辑。
输出的是子序列（元素保持原顺序，不一定连续），不是子数组（必须连续）。
存在多个相同长度的 LDS 时，上述 DP 方法返回其中一个（取决于遍历顺序和更新条件），如需全部结果，需改用回溯或记录所有可能路径。
简单测试验证
输入 [5, 3, 4, 8, 6, 7]：
- 递减子序列有：[5,3]、[5,4]、[8,6]、[8,7]、[6] 等
- 最长长度为 2，任一结果都合理
输入 [10, 9, 8, 7, 6]：LDS 就是整个数组，长度为 5。
