PHP-Programm für zusammenhängende Subarrays mit der größten Summe

Was ist PHP?

PHP (Hypertext Preprocessor) ist eine weit verbreitete serverseitige Skriptsprache für die Webentwicklung. Es ermöglicht Entwicklern, Code in HTML-Dateien einzubetten und so dynamische Webseiten und Interaktionen mit Datenbanken zu erstellen. PHP ist bekannt für seine Einfachheit, Vielseitigkeit und umfangreichen Integrationsmöglichkeiten mit gängigen Datenbanken. Es bietet eine breite Palette an Erweiterungen und verfügt über eine große Entwickler-Community, die umfangreiche Ressourcen und Support gewährleistet.

PHP-Programm für zusammenhängende Subarrays mit der größten Summe

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

Maximale zusammenhängende Summe ist = 6

Verwendung des Kadane-Algorithmus

Kadanes Algorithmus ist ein effizienter Algorithmus, der verwendet wird, um die maximale Summe eines zusammenhängenden Subarrays innerhalb eines bestimmten Arrays zu ermitteln. Es wurde 1984 von Jay Kadane entwickelt.

Der Algorithmus scannt das Array iterativ und verwaltet zwei Variablen: max_so_far und max_ending_here. So funktioniert der Algorithmus:

• Initialisieren Sie die Variablen max_so_far und max_ending_here auf das erste Element des Arrays oder auf einen Mindestwert (z. B. PHP_INT_MIN), wenn das Array negative Zahlen enthält.

• Durchlaufen Sie das Array ab dem zweiten Element.

• Aktualisieren Sie für jedes Element max_ending_here, indem Sie das aktuelle Element hinzufügen.

• Wenn max_ending_here negativ wird, setzen Sie es auf 0 zurück, da das Einschließen des aktuellen Elements in das Subarray die Summe verringert.

• Wenn max_ending_here größer als max_so_far ist, aktualisieren Sie max_so_far mit der neuen Maximalsumme.

• Wiederholen Sie die Schritte 3 bis 5 für die verbleibenden Elemente des Arrays.

• Nachdem das gesamte Array durchlaufen wurde, enthält max_so_far die maximale Summe eines zusammenhängenden Unterarrays.

• Max_so_far als Ergebnis zurückgeben.

Kadanes Algorithmus hat eine zeitliche Komplexität von O(n), wobei n die Größe des Arrays ist, da nur ein einziger Durchgang durch das Array erforderlich ist. Dies macht es zu einer effizienten Lösung zum Ermitteln der maximalen Summe zusammenhängender Subarrays.

Beispiel

<?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;
?>

Ausgabe

Maximum contiguous sum is 6

Verwendung eines algorithmischen Paradigmas: Dynamische Programmierung

Beispiel

<?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;
?>

Ausgabe

Maximum contiguous sum is 6

Ein anderer Ansatz mit Start- und Endindizes

Beispiel

<?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);
?>

Ausgabe

Maximum contiguous sum is 6 
Starting index 3 
Ending index 6

Fazit

Das PHP-Programm zum Finden des größten zusammenhängenden Subarrays nutzt dynamische Programmierung und Kadanes Algorithmus. Der Ansatz der dynamischen Programmierung wird verwendet, um das Problem effizient zu lösen, indem es in kleinere Teilprobleme zerlegt und die Lösungen in einem Array gespeichert wird.

Kadanes Algorithmus ist eine Schlüsselkomponente des Programms und dafür verantwortlich, das größte zusammenhängende Subarray zu finden. Es durchläuft das Array und aktualisiert kontinuierlich die aktuelle Summe, indem es entweder das aktuelle Element hinzufügt oder ein neues Unterarray startet. Die maximal gefundene Summe wird in der Variablen $maxSum gespeichert. Das Programm verarbeitet sowohl positive als auch negative Zahlen im Array effizient. Es identifiziert das Subarray mit der größten Summe, indem es die Start- und Endindizes verfolgt, was die Extraktion des Subarrays mit array_slice ermöglicht.

Durch die Verwendung dynamischer Programmierung und des Kadane-Algorithmus erreicht das Programm eine Zeitkomplexität von O(n), wobei n die Größe des Arrays ist. Dies gewährleistet eine effiziente Lösung zum Finden des größten zusammenhängenden Subarrays in PHP.

Das obige ist der detaillierte Inhalt vonPHP-Programm für zusammenhängende Subarrays mit der größten Summe. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!