PHP で連続する部分配列の最大合計を求める問題に対する 2 つの解決策

この記事では、PHP の配列の走査、判断、操作、およびその他の関連操作スキルを含む、PHP で連続部分配列の最大和を求める問題に対する 2 つの解決策を主に紹介します。必要な友人は参照してください。

この記事の例では、PHP で連続する部分配列の最大合計を求める問題に対する 2 つの解決策について説明します。参照用に全員と共有します。詳細は次のとおりです:

#問題の説明

#部分配列の最大合計を求めます

タイトルの説明:

整数配列を入力します。配列には正の数値と負の数値が含まれます。

配列内の 1 つ以上の連続する整数は部分配列を形成し、各部分配列には合計があります。
すべての部分配列の合計の最大値を見つけます。必要な時間計算量は
O(n) です。

連続する部分配列の最大和の問題に関しては、2 つの解決策があり、1 つは動的プログラミングです。

解決策は次のとおりです。

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

#スキャン方法もあります

##

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

#興味があるかもしれません 記事:

php ajax ヘッダーの取得メソッドとコンテンツ例の説明

Laravel で Queue を使用する最も基本的な操作チュートリアル

#Yaf フレームワーク PHPUnit 統合テスト方法の詳細説明

##

以上がPHP で連続する部分配列の最大合計を求める問題に対する 2 つの解決策の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。