最长递增子序列算法

最长递增子序列（Longest Increasing Subsequence, LIS）是计算机科学中的一个经典问题，目标是在给定的数列中找到一个非降序排列的子序列，使得该子序列的长度尽可能长。以下是一些解决最长递增子序列问题的算法：

1. 动态规划法（Dynamic Programming）：

   • 初始化一个长度为 n 的数组 dp，其中 dp[i] 表示以原序列中第 i 个元素结尾的最长递增子序列的长度。
   • 遍历输入序列，对于每个元素 a[i]，从 dp[0] 到 dp[i-1] 找出所有小于它的值对应的 dp[j]，更新 dp[i] 为这些值中的最大值加 1（因为当前元素可以加入到那些子序列末尾形成新的更长递增子序列）。
   • 最后，数组 dp 中的最大值即为原序列的最长递增子序列的长度。

2. 贪心 + 二分查找优化：

   • 在动态规划的基础上，可以进一步优化时间复杂度至 O(n log n)。
   • 维护一个有序序列（如使用堆或平衡二叉搜索树），用于存储当前递增子序列的末尾元素。
   • 对于每一个新元素，如果它比有序序列的末尾元素大，则将其添加到序列中；否则，用它替换有序序列中第一个大于它的元素，并调整有序序列保持递增。
   • 最后，有序序列的长度就是原序列的最长递增子序列长度。

3. 最长公共子序列变形法：

   • 将原序列排序，然后计算原序列和排序后的序列之间的最长公共子序列，但这通常不是最有效的解法，因为会改变原序列的相对顺序，可能会导致错误的结果。

在实际编程实现时，动态规划方法更为常用且易于理解，而结合贪心策略和二分查找的优化版本则可以有效降低时间复杂度，适用于大规模数据。

使用动态规划法

以下是一个使用动态规划法（简单朴素实现）在 PHP 中解决最长递增子序列问题的示例代码：

<?php

function longestIncreasingSubsequence($nums) {
    $n = count($nums);
    
    // 初始化 dp 数组，长度为 n+1，dp[0] 作为哨兵值
    $dp = array_fill(0, $n + 1, 1);
    
    // 遍历输入数组
    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            // 如果当前元素大于前一个元素，则可以形成更长的递增子序列
            if ($nums[$i - 1] > $nums[$j]) {
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
    }

    // 返回最长递增子序列的长度
    return max($dp);
}

// 测试数据
$nums = [10, 9, 2, 5, 3, 7, 101, 18];
$result = longestIncreasingSubsequence($nums);
echo "The length of the longest increasing subsequence is: ", $result;

?>

这个PHP代码将计算给定数组$nums的最长递增子序列的长度。

复杂度

上面的PHP代码实现的最长递增子序列算法使用了动态规划，其时间复杂度为O(n^2)，其中n是输入数组$nums的长度。这是因为有两个嵌套循环，外层循环遍历整个数组，内层循环则对每个元素之前的每个元素进行比较。

空间复杂度方面，该代码使用了一个大小为n+1的一维数组$dp来存储子问题的解，因此空间复杂度为O(n)。

使用贪心策略和二分查找

最长递增子序列问题可以通过结合贪心策略和二分查找进行优化，从而将时间复杂度降低到O(n log n)。

以下是使用PHP实现的优化版本：

<?php

// 定义一个二分查找函数，用于在动态规划数组中找到插入位置
function binarySearch(&$dp, $length, $target) {
    $left = 0;
    $right = $length - 1;

    // 通过二分查找确定目标值应该插入的位置
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        if ($dp[$mid] < $target) { // 目标值大于中间值，则在右半部分继续查找
            $left = $mid + 1;
        } else { // 目标值小于等于中间值，在左半部分或刚好就是中间位置
            $right = $mid - 1;
        }
    }

    // 返回插入位置（左边界+1，因为这里使用的是左闭右开区间）
    return $left;
}

// 使用贪心策略和二分查找优化的最长递增子序列算法
function longestIncreasingSubsequenceOptimized($nums) {
    $n = count($nums);

    // 初始化 dp 数组，长度为 n+1，前面填充 0，实际只用到前 n 个元素存储 LIS 的长度
    $dp = array_fill(0, $n + 1, 0);

    // tail 数组用来存储每个长度对应的LIS末尾元素，保持单调递增顺序
    $tail = array();

    // 遍历输入数组
    for ($i = 0; $i < $n; $i++) {
        // 通过二分查找确定当前数字 nums[$i] 在 dp 数组中的插入位置
        $pos = binarySearch($dp, $i, $nums[$i]);

        // 更新 dp 数组对应位置的值为当前遍历到的数，表示以这个数结尾的递增子序列长度
        $dp[$pos] = $nums[$i];

        // 更新 tail 数组，确保它始终包含各个长度递增子序列的最后一个元素，并且有序
        if ($pos == count($tail)) { // 当 pos 大于 tail 数组长度时，表示需要新增一个元素
            $tail[] = $nums[$i];
        } else {
            $tail[$pos] = $nums[$i]; // 替换 tail 数组中的某个元素，保持递增顺序
        }
    }

    // 返回最长递增子序列的长度，即 tail 数组的长度
    return count($tail);
}

// 测试数据
$nums = [10, 9, 2, 5, 3, 7, 101, 18];
$result = longestIncreasingSubsequenceOptimized($nums);
echo "The length of the longest increasing subsequence is: ", $result;

?>

在这个优化版本中，我们维护了一个单调递增数组$tail来记录当前已找到的所有递增子序列的最后一个元素，并且用一个辅助函数binarySearch()进行二分查找以快速定位新元素应插入的位置。

这样在遍历整个输入数组时，可以达到O(n log n)的时间复杂度。同时注意，这个版本只返回了最长递增子序列的长度，如果需要找出具体的递增子序列，还需要额外存储路径信息。

找出具体的递增子序列

为了找出最长递增子序列的具体元素，我们需要在实现中额外存储路径信息。这里提供一个基于上述优化算法的PHP代码示例，同时返回最长递增子序列的长度和具体序列：

<?php

function binarySearch(&$dp, $length, $target) {
    $left = 0;
    $right = $length - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        if ($dp[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return $left;
}

function longestIncreasingSubsequenceOptimized($nums) {
    $n = count($nums);
    $dp = array_fill(0, $n + 1, 0);
    $tail = array(); // 存储每个长度对应的LIS末尾元素
    $prevIndices = array_fill(0, $n + 1, null); // 存储前驱节点信息，用于回溯构建 LIS

    for ($i = 0; $i < $n; $i++) {
        $pos = binarySearch($dp, $i, $nums[$i]);
        $dp[$pos] = $nums[$i];
        $prevIndices[$pos] = $i; // 记录当前位置的前驱节点（原数组中的索引）

        // 更新 tail 数组，确保有序性
        if ($pos == count($tail)) {
            $tail[] = $nums[$i];
        } else {
            $tail[$pos] = $nums[$i];
        }
    }

    // 回溯构建最长递增子序列
    $lis = [];
    $idx = count($tail) - 1; // 最后一个有效位置对应最长递增子序列的最后一个元素
    while ($idx >= 0) {
        $lis[] = $nums[$prevIndices[$idx]]; // 添加当前元素到 LIS
        $idx = $prevIndices[$idx]; // 移动到前一个元素的位置
    }

    // 反转 LIS 以得到正确的顺序
    $lis = array_reverse($lis);

    // 返回最长递增子序列的长度及具体序列
    return [
        'length' => count($lis),
        'sequence' => $lis,
    ];
}

// 测试数据
$nums = [10, 9, 2, 5, 3, 7, 101, 18];
$result = longestIncreasingSubsequenceOptimized($nums);
echo "The length of the longest increasing subsequence is: ", $result['length'];
echo "\nThe longest increasing subsequence is: ", implode(', ', $result['sequence']);

?>

这段代码在计算最长递增子序列长度的同时，通过$prevIndices数组记录了每个位置的前驱节点，最后根据这些信息进行回溯，构造出具体的最长递增子序列。

欢迎关注公-众-号【TaonyDaily】、留言、评论，一起学习。

Don’t reinvent the wheel, library code is there to help.

文章来源：刘俊涛的博客

若有帮助到您，欢迎点赞、转发、支持，您的支持是对我坚持最好的肯定(^_)