Comment résoudre le plus grand sous-réseau et le problème en utilisant un algorithme gourmand en PHP

Comment résoudre le plus grand sous-réseau et le problème en utilisant un algorithme gourmand en PHP

Les sous-réseaux maximaux et le problème sont conçus pour trouver la somme maximale des sous-réseaux consécutifs dans un tableau. Les algorithmes gourmands sont devenus un moyen courant de résoudre ce problème en raison de leur simplicité et de leur efficacité. Cet article présentera comment utiliser des algorithmes gourmands pour implémenter la solution optimale à ce problème dans PHP et fournir des exemples de code détaillés.

Introduction à l'algorithme gourmand

L'idée principale des algorithmes gourmands est de sélectionner la solution optimale locale actuelle à chaque fois et de s'attendre à obtenir enfin la solution optimale globale à travers ces solutions optimales locales. Lors de la résolution du sous-réseau et du problème maximum, nous sélectionnons à chaque fois des éléments consécutifs dans le tableau, calculons leurs sommes et continuons à mettre à jour la somme maximale.

Étapes de la solution

Les étapes pour résoudre le plus grand sous-réseau et le problème à l'aide de l'algorithme gourmand sont les suivants:

• Initialisez les deux variables $ maxsum et $ currsum, respectivement, représentant la somme maximale actuellement trouvée et la somme du sous-réseau continu actuel.
• Itérer dans le tableau, pour chaque élément $ num, effectuez ce qui suit:
• Ajoutez l'élément actuel à $ currsum et mettez à jour $ currsum.
• Si $ currsum est supérieur à $ maxsum, mettez à jour $ maxsum.
• Si $ currsum est inférieur ou égal à 0, cela signifie que la contribution de la sous-bande actuelle à la somme suivante est négative et que $ currsum est réinitialisé à 0.
• Une fois la traversée terminée, $ maxsum est retourné, qui est la somme maximale de sous-réseau.

Exemple de code PHP

Voici un exemple de code PHP qui met en œuvre le plus grand sous-réseau et le plus problème:

 function findMaxSubarray($arr) {
    $maxSum = PHP_INT_MIN;
    $currSum = 0;

    foreach ($arr as $num) {
        $currSum += $num;

        if ($currSum > $maxSum) {
            $maxSum = $currSum;
        }

        if ($currSum <= 0) {
            $currSum = 0;
        }
    }

    return $maxSum;
}

// Exemple d&#39;utilisation
$arr = [1, -2, 3, 4, -5, 6, -7];
$maxSum = findMaxSubarray($arr);
echo 'La somme de la plus grande sous-réseau est：' . $maxSum;

Dans le code ci-dessus, nous parcourons le tableau et mettons à jour $ currsum et $ maxsum en fonction de la valeur de chaque élément. De cette façon, nous pouvons calculer la somme maximale de sous-réseau en une traversée.

Résumer

Cet article présente comment utiliser des algorithmes gourmands en PHP pour implémenter la solution optimale au plus grand sous-réseau et au problème. Grâce à cet algorithme, vous pouvez calculer efficacement la somme maximale du tableau et améliorer l'efficacité de l'algorithme dans le développement réel.