最长递减子序列指的是在一个给定的数组中，选取若干元素组成新的序列，新序列中的元素保持原数组的相对顺序，且每个后续元素都小于前一个元素，在所有满足条件的子序列中长度最长的就是最长递减子序列。在PHP中处理这类数组问题时，动态规划是常用且高效的实现思路。
动态规划实现原理
动态规划的核心思路是定义状态数组，记录每个位置的最长递减子序列长度，再通过状态转移得到最终结果。具体步骤如下：
- 定义
dp数组，dp[i]表示以原数组第i个元素结尾的最长递减子序列的长度，初始时每个元素的最长递减子序列至少是自身，所以dp数组所有元素初始化为1。 - 遍历原数组的每个元素，对于每个元素
i，再遍历它之前的所有元素j，如果arr[i] < arr[j]，说明arr[i]可以接在arr[j]结尾的递减子序列后面，此时更新dp[i]为max(dp[i], dp[j] + 1)。 - 遍历完
dp数组后，其中的最大值就是整个数组的最长递减子序列长度。
PHP完整实现代码
下面是使用PHP实现求数组最长递减子序列的完整代码，包含长度求解和子序列还原两部分：
<?php
/**
* 求数组的最长递减子序列
* @param array $arr 输入的原数组
* @return array 包含最长长度和对应子序列的数组
*/
function longestDecreasingSubsequence($arr) {
$len = count($arr);
if ($len == 0) {
return ['length' => 0, 'sequence' => []];
}
// 初始化dp数组，每个位置的最长递减子序列初始为1（自身）
$dp = array_fill(0, $len, 1);
// 记录前驱节点，用于还原子序列
$prev = array_fill(0, $len, -1);
$maxLen = 1;
$maxIndex = 0;
// 动态规划计算dp数组
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($arr[$i] < $arr[$j]) {
if ($dp[$j] + 1 > $dp[$i]) {
$dp[$i] = $dp[$j] + 1;
$prev[$i] = $j;
}
}
}
// 更新最大长度和对应索引
if ($dp[$i] > $maxLen) {
$maxLen = $dp[$i];
$maxIndex = $i;
}
}
// 还原最长递减子序列
$sequence = [];
$current = $maxIndex;
while ($current != -1) {
array_unshift($sequence, $arr[$current]);
$current = $prev[$current];
}
return [
'length' => $maxLen,
'sequence' => $sequence
];
}
// 测试示例
$testArr = [10, 9, 2, 5, 3, 7, 101, 18];
$result = longestDecreasingSubsequence($testArr);
echo "原数组：" . implode(', ', $testArr) . "<br/>";
echo "最长递减子序列长度：" . $result['length'] . "<br/>";
echo "最长递减子序列：" . implode(', ', $result['sequence']) . "<br/>";
?>
算法复杂度分析
上述实现的时间复杂度为O(n²)，其中n是输入数组的长度，因为使用了两层嵌套循环遍历数组元素。空间复杂度为O(n)，需要额外存储dp数组和prev数组，以及还原子序列的临时空间。
注意事项
- 如果原数组中存在相等元素，上述逻辑中相等元素不会构成递减关系，符合递减序列的严格定义，如果需要非严格递减（允许相等），只需要将判断条件
$arr[$i] < $arr[$j]修改为$arr[$i] <= $arr[$j]即可。 - 当输入数组为空时，函数会返回长度为0的空序列，避免后续逻辑报错。
- 还原子序列时使用
array_unshift是因为前驱节点是从后往前记录的，需要把元素按顺序插入到结果数组的开头。