PHP implémente deux solutions au problème de la recherche de la somme maximale de sous-tableaux consécutifs

Cet article présente principalement deux solutions au problème de la recherche de la somme maximale de sous-tableaux consécutifs en PHP, impliquant la traversée de tableaux, le jugement, le calcul et d'autres compétences opérationnelles connexes de PHP. Les amis dans le besoin peuvent s'y référer

. Les exemples de cet article décrivent deux solutions au problème de la recherche de la somme maximale de sous-tableaux consécutifs en PHP. Partagez-le avec tout le monde pour référence, comme suit :

Description du problème

Trouver la somme maximale des sous-tableaux

Description du titre :

Saisissez un tableau d'entiers, il y a des nombres positifs et négatifs dans le tableau.
Un ou plusieurs entiers consécutifs dans le tableau forment un sous-tableau, et chaque sous-tableau a une somme.
Trouvez la somme maximale de tous les sous-tableaux. La complexité temporelle requise est O(n).

Concernant le problème de la somme maximale des sous-tableaux consécutifs, il existe deux solutions. L'une est la programmation dynamique

La solution est la suivante :

function getMaxSubSum($arr){
  $curSum = $arr[0];
  $maxSum = $arr[0];
  for($i = 1; $i < count($arr); $i++){
    if($curSum > 0) $curSum += $arr[$i];
    else $curSum = $arr[$i];
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  return $maxSum;
}

Il existe également la méthode de numérisation

function getMaxSubSum($arr){
  $curSum = 0;
  $maxSum = 0;
  for($i = 0; $i < count($arr); $i++ ){
    $curSum += $arr[$i];
    if($curSum <= 0) $curSum = 0;
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  if($maxSum == 0){
    $maxSum = $arr[0];
    for($i = 1; $i < count($arr); $i++){
      if($maxSum < $arr[$i] ) $maxSum = $arr[$i];
    }
  }
  return $maxSum;
}

Articles qui pourraient vous intéresser :

Explication de la méthode des headers et du contenu de php pour obtenir ajax

Les plus basiques tutoriel d'utilisation de Queue dans Laravel Explain

Explication détaillée de la méthode de test d'intégration PHPUnit du framework Yaf

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!