How to write the longest increasing subsequence algorithm using PHP

How to use PHP to write the longest increasing subsequence algorithm

Introduction:
The longest increasing subsequence is a classic computing problem. It is to find the longest increasing subsequence in a sequence. . In computer science, there are many solutions to this problem, one of which is dynamic programming. This article will introduce how to write the longest increasing subsequence algorithm using PHP and provide code examples.

Step 1: Understand the longest increasing subsequence problem
Before starting to write the algorithm, you must first understand the definition of the longest increasing subsequence. Given a sequence A, we want to find the longest subsequence B such that B is strictly increasing. For example, for the sequence A = [2, 4, 3, 5, 1, 7, 6, 9, 8], its longest increasing subsequence is B = [2, 3, 5, 7, 9], with a length of 5.

Step 2: Use dynamic programming to solve the problem
Dynamic programming is an effective method to solve the longest increasing subsequence problem. We can record the length of the longest increasing subsequence ending with A[i] through an array dp[i]. Next, we get the length of the longest increasing subsequence by looping through the array A and updating the dp array.

Code example:
The following is a sample code for the longest increasing subsequence algorithm written in PHP:

function longestIncreasingSubsequence($arr) {
    $n = count($arr);
    $dp = array_fill(0, $n, 1); // 初始化 dp 数组，每个元素的初始值都为 1

    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$i] > $arr[$j]) {
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
    }

    $maxLength = max($dp); // 最长递增子序列的长度

    return $maxLength;
}

$arr = [2, 4, 3, 5, 1, 7, 6, 9, 8];
$length = longestIncreasingSubsequence($arr);
echo "最长递增子序列的长度为：".$length;

Running the above code will output the length of the longest increasing subsequence as 5 , consistent with our previous example.

Step 3: Optimization algorithm
Through the above dynamic programming algorithm, we can get the length of the longest increasing subsequence, but we cannot get the specific subsequence. If we also want to get the specific elements of the longest increasing subsequence, we can slightly optimize the algorithm.

Code example:
The following is a further optimized example code for the longest increasing subsequence algorithm:

function longestIncreasingSubsequence($arr) {
    $n = count($arr);
    $dp = array_fill(0, $n, 1); // 初始化 dp 数组，每个元素的初始值都为 1

    for ($i = 1; $i < $n; $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; // 记录递增子序列的上一个元素的下标
                }
            }
        }
    }

    $maxLength = max($dp); // 最长递增子序列的长度

    // 构建最长递增子序列
    $index = array_search($maxLength, $dp);
    $lis = [];
    while ($index !== null) {
        $lis[] = $arr[$index];
        $index = $prev[$index] ?? null;
    }

    $lis = array_reverse($lis); // 反转子序列，得到递增顺序

    return [
        'length' => $maxLength,
        'sequence' => $lis
    ];
}

$arr = [2, 4, 3, 5, 1, 7, 6, 9, 8];
$result = longestIncreasingSubsequence($arr);
echo "最长递增子序列的长度为：".$result['length']."
";
echo "最长递增子序列为：".implode(', ', $result['sequence']);

Running the above code will output the length of the longest increasing subsequence as 5, And print the longest increasing subsequence as [2, 3, 5, 7, 9].

Summary:
This article introduces how to write the longest increasing subsequence algorithm using PHP and provides code examples. Through the idea of ​​dynamic programming, we can efficiently solve the problem of the longest increasing subsequence. I hope this article will be helpful to readers who want to learn and use the longest increasing subsequence algorithm.

The above is the detailed content of How to write the longest increasing subsequence algorithm using PHP. For more information, please follow other related articles on the PHP Chinese website!