Programme PHP pour le sous-tableau contigu de la plus grande somme

Qu'est-ce que PHP ?

PHP (Hypertext Preprocessor) est un langage de script côté serveur largement utilisé pour le développement Web. Il permet aux développeurs d'intégrer du code dans des fichiers HTML, permettant la création de pages Web dynamiques et d'interactions avec des bases de données. PHP est connu pour sa simplicité, sa polyvalence et ses capacités d'intégration étendues avec les bases de données populaires. Il propose une large gamme d'extensions et dispose d'une large communauté de développeurs, garantissant des ressources et un support suffisants.

Programme PHP pour le sous-tableau contigu à la plus grande somme

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

La somme contiguë maximale est = 6

Utilisation de l'algorithme de Kadane

L'algorithme de Kadane est un algorithme efficace utilisé pour trouver la somme maximale d'un sous-tableau contigu dans un tableau donné. Il a été développé par Jay Kadane en 1984.

L'algorithme fonctionne en analysant le tableau de manière itérative et en conservant deux variables : max_so_far et max_ending_here. Voici comment fonctionne l'algorithme :

• Initialisez les variables max_so_far et max_ending_here au premier élément du tableau ou à une valeur minimale (par exemple, PHP_INT_MIN) si le tableau contient des nombres négatifs.

• Parcourez le tableau à partir du deuxième élément.

• Pour chaque élément, mettez à jour max_ending_here en y ajoutant l'élément actuel.

• Si max_ending_here devient négatif, réinitialisez-le à 0 car l'inclusion de l'élément actuel dans le sous-tableau diminuera la somme.

• Si max_ending_here est supérieur à max_so_far, mettez à jour max_so_far avec la nouvelle somme maximale.

• Répétez les étapes 3 à 5 pour les éléments restants du tableau.

• Après avoir parcouru l'ensemble du tableau, max_so_far contiendra la somme maximale d'un sous-tableau contigu.

• Renvoyer max_so_far comme résultat.

L'algorithme de Kadane a une complexité temporelle de O(n), où n est la taille du tableau, car il ne nécessite qu'un seul passage à travers le tableau. Cela en fait une solution efficace pour trouver la somme maximale du sous-tableau contigu.

Exemple

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

Sortie

Maximum contiguous sum is 6

Utiliser le paradigme algorithmique : programmation dynamique

Exemple

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

Sortie

Maximum contiguous sum is 6

Une autre approche avec des index de début et de fin

Exemple

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

Sortie

Maximum contiguous sum is 6 
Starting index 3 
Ending index 6

Conclusion

Le programme PHP permettant de trouver le sous-tableau contigu de la plus grande somme utilise la programmation dynamique et l'algorithme de Kadane. L'approche de programmation dynamique est utilisée pour résoudre efficacement le problème en le décomposant en sous-problèmes plus petits et en stockant les solutions dans un tableau.

L'algorithme de Kadane est un élément clé du programme et est chargé de trouver le sous-tableau contigu à la plus grande somme. Il parcourt le tableau, mettant continuellement à jour la somme actuelle en ajoutant l'élément actuel ou en démarrant un nouveau sous-tableau. La somme maximale rencontrée est stockée dans la variable $maxSum. Le programme gère efficacement les nombres positifs et négatifs du tableau. Il identifie le sous-tableau avec la plus grande somme en gardant une trace des indices de début et de fin, permettant l'extraction du sous-tableau à l'aide de array_slice.

En utilisant la programmation dynamique et l'algorithme de Kadane, le programme atteint une complexité temporelle de O(n), où n est la taille du tableau. Cela garantit une solution efficace pour trouver le sous-tableau contigu à la plus grande somme en PHP.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!