So schreiben Sie den am längsten ansteigenden Teilsequenzalgorithmus mit PHP

So schreiben Sie den Algorithmus für die am längsten ansteigende Teilsequenz mit PHP

Einführung:
Die am längsten ansteigende Teilsequenz ist ein klassisches Rechenproblem, bei dem es darum geht, die am längsten ansteigende Teilsequenz in einer Sequenz zu finden. In der Informatik gibt es viele Lösungen für dieses Problem, eine davon ist die dynamische Programmierung. In diesem Artikel wird erläutert, wie Sie mit PHP den am längsten ansteigenden Teilsequenzalgorithmus schreiben, und es werden Codebeispiele bereitgestellt.

Schritt 1: Verstehen Sie das Problem der am längsten ansteigenden Teilsequenz
Bevor Sie mit dem Schreiben des Algorithmus beginnen, müssen Sie zunächst die Definition der am längsten ansteigenden Teilsequenz verstehen. Gegeben sei eine Folge A, wir wollen die längste Teilfolge B finden, sodass B streng wachsend ist. Beispielsweise ist für die Folge A = [2, 4, 3, 5, 1, 7, 6, 9, 8] die längste ansteigende Teilfolge B = [2, 3, 5, 7, 9] mit einer Länge von 5.

Schritt 2: Verwenden Sie dynamische Programmierung, um das Problem zu lösen.
Dynamische Programmierung ist eine effektive Methode, um das Problem der am längsten zunehmenden Teilsequenz zu lösen. Wir können die Länge der am längsten ansteigenden Teilsequenz, die mit A[i] endet, über ein Array dp[i] aufzeichnen. Als nächstes ermitteln wir die Länge der am längsten ansteigenden Teilsequenz, indem wir das Array A durchlaufen und das dp-Array aktualisieren.

Codebeispiel:
Hier ist ein Beispielcode für den in PHP geschriebenen Algorithmus für die am längsten ansteigende Teilsequenz:

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;

Beim Ausführen des obigen Codes wird die Länge der am längsten ansteigenden Teilsequenz von 5 ausgegeben, im Einklang mit unserem vorherigen Beispiel.

Schritt 3: Optimierungsalgorithmus
Durch den obigen dynamischen Programmieralgorithmus können wir die Länge der am längsten ansteigenden Teilsequenz ermitteln, aber nicht die spezifische Teilsequenz. Wenn wir auch die spezifischen Elemente der am längsten wachsenden Teilfolge erhalten möchten, können wir den Algorithmus leicht optimieren.

Codebeispiel:
Das Folgende ist ein weiter optimierter Beispielcode für den am längsten ansteigenden Teilsequenzalgorithmus:

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']."<br>";
echo "最长递增子序列为：".implode(', ', $result['sequence']);

Durch Ausführen des obigen Codes wird die Länge der am längsten ansteigenden Teilsequenz als 5 ausgegeben und die Länge der am längsten ansteigenden Teilsequenz als ausgegeben [2, 3, 5, 7, 9].

Zusammenfassung:
Dieser Artikel stellt vor, wie man den am längsten ansteigenden Teilsequenzalgorithmus mit PHP schreibt, und stellt Codebeispiele bereit. Durch die Idee der dynamischen Programmierung können wir das Problem der am längsten wachsenden Teilsequenz effizient lösen. Ich hoffe, dass dieser Artikel für Leser hilfreich ist, die den am längsten zunehmenden Teilsequenzalgorithmus erlernen und verwenden möchten.

Das obige ist der detaillierte Inhalt vonSo schreiben Sie den am längsten ansteigenden Teilsequenzalgorithmus mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!