連続サブ配列の最大合計値を求める PHP プログラム

PHPとは何ですか?

PHP (ハイパーテキスト プリプロセッサ) は、Web 開発で広く使用されているサーバーサイド スクリプト言語です。これにより、開発者は HTML ファイル内にコードを埋め込むことができ、動的な Web ページの作成やデータベースとの対話が可能になります。 PHP は、そのシンプルさ、多用途性、および一般的なデータベースとの広範な統合機能で知られています。幅広い拡張機能を提供し、大規模な開発者コミュニティがあり、十分なリソースとサポートが確保されています。

最大合計の連続部分配列を求める PHP プログラム

4+(-1)+2+1=6

連続する合計の最大値は = 6

Kadane のアルゴリズムの使用

Kadane のアルゴリズムは、指定された配列内の連続する部分配列の最大合計を見つけるために使用される効率的なアルゴリズムです。 1984 年にジェイ・カダンによって開発されました。

このアルゴリズムは、配列を繰り返しスキャンし、max_so_far と max_ending_here の 2 つの変数を維持することによって機能します。アルゴリズムの仕組みは次のとおりです。

• max_so_far 変数と max_ending_here 変数を配列の最初の要素に初期化するか、配列に負の数が含まれる場合は最小値 (PHP_INT_MIN など) に初期化します。

• 2 番目の要素以降、配列を反復処理します。

• 各要素について、現在の要素を追加して max_ending_here を更新します。

• max_ending_here が負になった場合は、部分配列に現在の要素を含めると合計が減少するため、0 にリセットします。

• max_ending_here が max_so_far より大きい場合、max_so_far を新しい最大合計で更新します。

• 配列の残りの要素に対して手順 3 ～ 5 を繰り返します。

• 配列全体を反復した後、max_so_far は連続する部分配列の最大合計を保持します。

• 結果として max_so_far を返します。

Kadane のアルゴリズムは、配列を 1 回通過するだけで済むため、時間計算量は O(n) です。n は配列のサイズです。これは、連続する部分配列の最大合計を見つけるための効率的なソリューションになります。

例

リーリー

出力

リーリー

アルゴリズム パラダイムの使用: 動的プログラミング

例

リーリー

出力

リーリー

開始インデックスと終了インデックスを使用した別のアプローチ

例

リーリー

出力

リーリー

結論

最大合計の連続部分配列を見つけるための PHP プログラムは、動的プログラミングと Kadane のアルゴリズムを利用しています。動的プログラミング アプローチは、問題をより小さなサブ問題に分割し、その解を配列に格納することにより、問題を効率的に解決するために採用されています。

Kadane のアルゴリズムはプログラムの重要なコンポーネントであり、連続する部分配列の合計の最大値を見つける役割を果たします。配列を反復処理し、現在の要素を追加するか、新しいサブ配列を開始することによって、現在の合計を継続的に更新します。発生した最大合計は $maxSum 変数に保存されます。このプログラムは、配列内の正の数値と負の数値の両方を効率的に処理します。開始インデックスと終了インデックスを追跡することで合計が最大のサブ配列を特定し、array_slice を使用してサブ配列を抽出できるようにします。

動的計画法と Kadane のアルゴリズムを利用することにより、プログラムは O(n) の時間計算量を達成します。ここで、n は配列のサイズです。これにより、PHP で連続サブ配列の合計の最大値を見つけるための効率的なソリューションが保証されます。

以上が連続サブ配列の最大合計値を求める PHP プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。