PHPとは何ですか？

PHP（HyperText Preprocessor）は、Web開発のために広く使用されているサーバー側のスクリプト言語です。開発者はHTMLファイルにコードを埋め込み、動的なWebページの作成とデータベースとのやり取りを可能にします。 PHPは、その単純さ、汎用性、および一般的なデータベースとの広範な統合機能で知られています。幅広い拡張機能を提供し、開発者の大規模なコミュニティがあり、十分なリソースとサポートを確保しています。

最大の合計隣接サブアレイのためのPHPプログラム

4（-1）2 1 = 6

最大隣接合計は= 6です

Kadaneのアルゴリズムを使用

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

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

• Arrayの最初の要素または最小値（たとえば、PHP_INT_MIN）にArrayに負の数値が含まれている場合、MAX_SO_FARおよびMAX_ENDING_HEARの変数を初期化します。

• は、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のアルゴリズムには、O（n）の時間の複雑さがあります。ここで、nは配列のサイズです。アレイを単一のパスを必要とするだけです。これにより、最大合計隣接サブアレイを見つけるための効率的なソリューションになります。

例

出力

Maximum contiguous sum is 6

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

例

出力

Maximum contiguous sum is 6

スタートとエンドのインデックスを使用した別のアプローチ

例

";
	echo "Starting index ". $start . "
".
			"Ending index " . $end . "
";
}
// Driver Code
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = sizeof($a);
$max_sum = maxSubArraySum($a, $n);
?>

出力

Maximum contiguous sum is 6 
Starting index 3 
Ending index 6

結論

最大の合計隣接サブアレイを見つけるためのPHPプログラムは、動的プログラミングとKadaneのアルゴリズムを利用しています。動的プログラミングアプローチは、問題をより小さなサブ問題に分解し、配列にソリューションを保存することにより、問題を効率的に解決するために採用されています。

Kadaneのアルゴリズムはプログラムの重要なコンポーネントであり、最大の合計隣接サブアレイを見つける責任があります。アレイを繰り返し、現在の要素を追加するか、新しいサブアレイを起動することにより、現在の合計を継続的に更新します。遭遇する最大合計は、 $ maxsum変数に保存されます。このプログラムは、配列内の正と負の両方の数を効率的に処理します。スタートとエンドのインデックスを追跡し、array_sliceを使用してサブアレイを抽出できるようにすることにより、最大の合計でサブアレイを識別します。

動的プログラミングとKadaneのアルゴリズムを利用することにより、プログラムはO（n）の時間の複雑さを達成します。ここで、nは配列のサイズです。これにより、PHPで最大の合計隣接サブアレイを見つけるための効率的なソリューションが保証されます。