Bagaimana untuk menulis algoritma urutan yang paling lama meningkat menggunakan PHP

Cara menulis algoritma urutan terpanjang yang meningkat menggunakan PHP

Pengenalan:
Jujukan yang paling lama meningkat ialah masalah pengkomputeran klasik, iaitu mencari urutan yang meningkat terpanjang dalam urutan. Dalam sains komputer, terdapat banyak penyelesaian kepada masalah ini, salah satunya ialah pengaturcaraan dinamik. Artikel ini akan memperkenalkan cara menulis algoritma urutan terpanjang yang meningkat menggunakan PHP dan memberikan contoh kod. . Diberi urutan A, kita ingin mencari urutan B terpanjang supaya B meningkat dengan tegas. Contohnya, untuk jujukan A = [2, 4, 3, 5, 1, 7, 6, 9, 8], jujukan peningkatan terpanjangnya ialah B = [2, 3, 5, 7, 9], dengan panjang daripada 5.

Langkah 2: Gunakan pengaturcaraan dinamik untuk menyelesaikan masalah
Pengaturcaraan dinamik ialah kaedah yang berkesan untuk menyelesaikan masalah seterusnya yang semakin lama semakin meningkat. Kita boleh merekodkan kepanjangan bagi jujukan yang meningkat terpanjang yang berakhir dengan A[i] melalui tatasusunan dp[i]. Seterusnya, kita mendapat panjang urutan terpanjang yang meningkat dengan menggelung melalui tatasusunan A dan mengemas kini tatasusunan dp.

Contoh Kod:
Berikut ialah contoh kod untuk algoritma susulan yang meningkat paling lama yang ditulis dalam 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;

Menjalankan kod di atas akan mengeluarkan panjang susulan peningkatan terpanjang sebanyak 5, selaras dengan contoh kami sebelum ini.

Langkah 3: Algoritma Pengoptimuman

Melalui algoritma pengaturcaraan dinamik di atas, kita boleh mendapatkan panjang urutan yang paling lama meningkat, tetapi kita tidak boleh mendapatkan urutan tertentu. Jika kita juga ingin mendapatkan elemen khusus bagi urutan yang paling lama meningkat, kita boleh sedikit mengoptimumkan algoritma.

Contoh kod:
Berikut ialah kod contoh yang dioptimumkan lagi untuk algoritma susulan yang paling lama meningkat:

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']);

Menjalankan kod di atas akan mengeluarkan panjang susulan yang paling lama meningkat sebagai 5, dan mencetak panjang susulan yang paling lama meningkat sebagai [2 , 3, 5, 7, 9].

Ringkasan:

Artikel ini memperkenalkan cara menulis algoritma urutan terpanjang yang meningkat menggunakan PHP dan menyediakan contoh kod. Melalui idea pengaturcaraan dinamik, kami boleh menyelesaikan masalah urutan yang paling lama meningkat dengan cekap. Saya harap artikel ini akan membantu pembaca yang ingin belajar dan menggunakan algoritma urutan yang semakin lama semakin meningkat.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma urutan yang paling lama meningkat menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!