PHP implementiert zwei Lösungen für das Problem, die maximale Summe aufeinanderfolgender Subarrays zu finden

In diesem Artikel werden hauptsächlich zwei Lösungen für das Problem des Ermittelns der maximalen Summe aufeinanderfolgender Subarrays in PHP vorgestellt, die die Array-Durchquerung, Beurteilung, Berechnung und andere damit verbundene Bedienfähigkeiten von PHP umfassen

Die Beispiele in diesem Artikel beschreiben zwei Lösungen für das Problem, die maximale Summe aufeinanderfolgender Subarrays in PHP zu finden. Geben Sie es wie folgt als Referenz an alle weiter:

Problembeschreibung

Ermitteln Sie die maximale Summe von Unterarrays

Titelbeschreibung:

Geben Sie ein ganzzahliges Array ein. Das Array enthält positive und negative Zahlen.
Eine oder mehrere aufeinanderfolgende ganze Zahlen im Array bilden ein Unterarray, und jedes Unterarray hat eine Summe.
Ermitteln Sie die maximale Summe aller Subarrays. Die erforderliche Zeitkomplexität beträgt O(n).

Für das Problem der maximalen Summe aufeinanderfolgender Subarrays gibt es zwei Lösungen. Eine davon ist die dynamische Programmierung

Die Lösung lautet wie folgt:

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

Es gibt auch eine Scan-Methode

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

Sie könnten interessiert sein Artikel:

Erklärung der Header-Methode und des Inhalts von PHP zum Erhalten von Ajax

Erklärung des grundlegendsten Bedienungs-Tutorials von Verwenden von Queue in Laravel

Detaillierte Erläuterung der PHPUnit-Integrationstestmethode des Yaf-Frameworks

Das obige ist der detaillierte Inhalt vonPHP implementiert zwei Lösungen für das Problem, die maximale Summe aufeinanderfolgender Subarrays zu finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!