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 les bases de données. PHP est connu pour sa simplicité, sa polyvalence et ses grandes capacités d'intégration avec des bases de données populaires. Il offre un large éventail d'extensions et possède une grande communauté de développeurs, garantissant de nombreuses ressources et soutien.

Programme PHP pour la plus grande somme subarray contigu

4 (-1) 2 1 = 6

La somme contigu maximale est = 6

en utilisant l'algorithme de Kadane

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

L'algorithme fonctionne en numérisant itérativement le tableau et en maintenant 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.

• itérer dans 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 parce que l'inclusion de l'élément actuel dans le sous-réseau 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 itérant le tableau entier, max_so_far conservera la somme maximale d'un sous-réseau contigu.

• renvoie max_so_far en résultat.

L'algorithme de Kadane a une complexité temporelle d'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 le sous-réseau contigu maximum.

Exemple

Sortir

Maximum contiguous sum is 6

Utilisation du paradigme algorithmique: programmation dynamique

Exemple

Sortir

Maximum contiguous sum is 6

une autre approche avec des index de démarrage

Exemple

";
	echo "Starting index ". $start . "
".
			"Ending index " . $end . "
";
}
// Driver Code
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = sizeof($a);
$max_sum = maxSubArraySum($a, $n);
?>

Sortir

Maximum contiguous sum is 6 
Starting index 3 
Ending index 6

Conclusion

Le programme PHP pour trouver la plus grande somme sous-réseau contigu 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 la décomposant en sous-problèmes plus petits et en stockant les solutions dans un tableau.

L'algorithme de Kadane est un composant clé du programme et est responsable de la recherche de la plus grande somme sous-réseau contigu. Il itère sur le tableau, mettant à jour en continu la somme actuelle en ajoutant l'élément actuel ou en démarrant un nouveau sous-réseau. La somme maximale rencontrée est stockée dans la variable $ maxsum. Le programme gère efficacement les nombres positifs et négatifs dans le tableau. Il identifie le sous-réseau avec la plus grande somme en gardant une trace des indices de début et de fin, permettant l'extraction du sous-réseau à l'aide d'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 la plus grande somme sous-réseau contigu en PHP.