Program PHP untuk Jumlah Terbesar Subarray Bersebelahan

Apakah itu PHP?

PHP (Hypertext Preprocessor) ialah bahasa skrip bahagian pelayan yang digunakan secara meluas untuk pembangunan web. Ia membolehkan pembangun membenamkan kod dalam fail HTML, membolehkan penciptaan halaman web dinamik dan interaksi dengan pangkalan data. PHP terkenal dengan kesederhanaan, serba boleh dan keupayaan penyepaduan yang meluas dengan pangkalan data yang popular. Ia menawarkan rangkaian sambungan yang luas dan mempunyai komuniti pembangun yang besar, memastikan sumber dan sokongan yang mencukupi.

Program PHP untuk Jumlah Terbesar Subarray Bersebelahan

4+ (-1) +2 +1 = 6

Jumlah bersebelahan maksimum ialah = 6

Menggunakan Algoritma Kadane

Algoritma Kadane ialah algoritma cekap yang digunakan untuk mencari jumlah maksimum subarray bersebelahan dalam tatasusunan tertentu. Ia telah dibangunkan oleh Jay Kadane pada tahun 1984.

Algoritma berfungsi dengan mengimbas tatasusunan secara berulang dan mengekalkan dua pembolehubah: max_so_far dan max_ending_here. Begini cara algoritma berfungsi:

• Memulakan pembolehubah max_so_far dan max_ending_here kepada elemen pertama tatasusunan atau kepada nilai minimum (cth., PHP_INT_MIN) jika tatasusunan mengandungi nombor negatif.

• Lelaran melalui tatasusunan dari elemen kedua dan seterusnya.

• Untuk setiap elemen, kemas kini max_ending_here dengan menambahkan elemen semasa padanya.

• Jika max_ending_here menjadi negatif, tetapkan semula kepada 0 kerana memasukkan elemen semasa dalam subarray akan mengurangkan jumlahnya.

• Jika max_ending_here lebih besar daripada max_so_far, kemas kini max_so_far dengan jumlah maksimum baharu.

• Ulang langkah 3 hingga 5 untuk baki elemen tatasusunan.

• Selepas melelaran melalui keseluruhan tatasusunan, max_so_far akan memegang jumlah maksimum subarray bersebelahan.

• Kembalikan max_so_far sebagai hasilnya.

Algoritma Kadane mempunyai kerumitan masa O(n), dengan n ialah saiz tatasusunan, kerana ia hanya memerlukan satu laluan melalui tatasusunan. Ini menjadikannya penyelesaian yang cekap untuk mencari jumlah maksimum subarray bersebelahan.

Contoh

<?php
// PHP program to print largest
// contiguous array sum
function maxSubArraySum($a, $size)
{
	$max_so_far = PHP_INT_MIN;
	$max_ending_here = 0;
	for ($i = 0; $i < $size; $i++)
	{
		$max_ending_here = $max_ending_here + $a[$i];
		if ($max_so_far < $max_ending_here)
			$max_so_far = $max_ending_here;

		if ($max_ending_here < 0)
			$max_ending_here = 0;
	}
	return $max_so_far;
}
// Driver code
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = count($a);
$max_sum = maxSubArraySum($a, $n);
echo "Maximum contiguous sum is " ,
						$max_sum;
?>

Output

Maximum contiguous sum is 6

Menggunakan Paradigma Algoritma: Pengaturcaraan Dinamik

Contoh

<?php
function maxSubArraySum($a, $size)
{
	$max_so_far = $a[0];
	$curr_max = $a[0];
	for ($i = 1; $i < $size; $i++)
	{
		$curr_max = max($a[$i],
						$curr_max + $a[$i]);
		$max_so_far = max($max_so_far,
						$curr_max);
	}
	return $max_so_far;
}
// Driver Code
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = sizeof($a);
$max_sum = maxSubArraySum($a, $n);
echo "Maximum contiguous sum is " .
						$max_sum;
?>

Output

Maximum contiguous sum is 6

Pendekatan lain dengan indeks permulaan dan akhir

Contoh

<?php
// PHP program to print largest
// contiguous array sum
function maxSubArraySum($a, $size)
{
	$max_so_far = PHP_INT_MIN;
	$max_ending_here = 0;
	$start = 0;
	$end = 0;
	$s = 0;
	for ($i = 0; $i < $size; $i++)
	{
		$max_ending_here += $a[$i];

		if ($max_so_far < $max_ending_here)
		{
			$max_so_far = $max_ending_here;
			$start = $s;
			$end = $i;
		}
		if ($max_ending_here < 0)
		{
			$max_ending_here = 0;
			$s = $i + 1;
		}
	}
	echo "Maximum contiguous sum is ".
					$max_so_far."<br>";
	echo "Starting index ". $start . "<br>".
			"Ending index " . $end . "<br>";
}
// Driver Code
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = sizeof($a);
$max_sum = maxSubArraySum($a, $n);
?>

Output

Maximum contiguous sum is 6 
Starting index 3 
Ending index 6

Kesimpulan

Program PHP untuk mencari jumlah subarray bersebelahan terbesar menggunakan pengaturcaraan dinamik dan algoritma Kadane. Pendekatan pengaturcaraan dinamik digunakan untuk menyelesaikan masalah dengan cekap dengan memecahkannya kepada sub masalah yang lebih kecil dan menyimpan penyelesaian dalam tatasusunan.

Algoritma Kadane ialah komponen utama program dan bertanggungjawab untuk mencari jumlah subarray bersebelahan terbesar. Ia berulang ke atas tatasusunan, mengemas kini jumlah semasa secara berterusan dengan sama ada menambah elemen semasa atau memulakan subarray baharu. Jumlah maksimum yang ditemui disimpan dalam pembolehubah $maxSum. Program ini mengendalikan kedua-dua nombor positif dan negatif dalam tatasusunan dengan cekap. Ia mengenal pasti subarray dengan jumlah terbesar dengan menjejaki indeks mula dan akhir, membenarkan pengekstrakan subarray menggunakan array_slice.

Dengan menggunakan pengaturcaraan dinamik dan algoritma Kadane, program ini mencapai kerumitan masa O(n), dengan n ialah saiz tatasusunan. Ini memastikan penyelesaian yang cekap untuk mencari jumlah subarray bersebelahan terbesar dalam PHP.

Atas ialah kandungan terperinci Program PHP untuk Jumlah Terbesar Subarray Bersebelahan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!