最大合計で部分配列のサイズを計算する JavaScript プログラム

#JavaScript プログラムで最大サイズとサブ配列サイズを見つけることは、プログラミングの世界、特に Web 開発の世界ではよくある問題です。この問題ステートメントには、指定された 1 次元の整数配列内で最大合計を持つ連続した部分配列を見つけることが含まれます。これは最大部分配列問題としても知られています。この問題を解決すると、財務分析、株式市場予測、信号処理などのさまざまなアプリケーションに役立ちます。

この記事では、JavaScript を使用して最大合計を達成するためのアルゴリズムと部分配列のサイズについて説明します。まず問題について詳しく説明し、次に JavaScript プログラミング言語を使用した段階的な解決策の開発に進みます。それでは始めましょう!

＃＃＃問題文＃＃＃

整数の配列が与えられた場合、合計が最大となる部分配列の長さを見つけなければなりません。

たとえば、整数の配列 [1, -2, 1, 1, -2, 1] があり、最大の部分配列は [1, 1]、合計は 2 であるとします。この部分配列の長さは、終了インデックスから開始インデックスを減算し、1 を加算することで求めることができます。この例では、開始インデックスは 0、終了インデックスは 1 であるため、部分配列の長さは 2 です。

別の例は、すべての負の整数の配列です: [-2, -5, -8, -3, -1, -7]。この場合、最大の部分配列は [-1] になり、合計は -1 になります。すべての要素が負であるため、絶対値が最小の部分配列の合計が最大になります。したがって、部分配列の長さは -1 になります。

最大サブ配列は複数存在する可能性があり、各サブ配列の合計は同じであることに注意してください。ただし、そのうちの 1 つを見つける必要があるだけです。

＃＃＃アルゴリズム＃＃＃ ＃＃＃ステップ1＃＃＃

最初に 4 つの変数を初期化します。「maxSum」は「-Infinity」、「currentSum」は「0」、「start」は「0」、end は「0」です。 「maxSum」を使用してこれまでに確認した最大の合計を追跡し、「currentSum」を使用して現在の反復の部分配列の合計を計算し、「start」を使用して部分配列の開始インデックスを追跡します。サブ配列の終了インデックスを追跡するための「end」。

＃＃＃ステップ2＃＃＃

次に、「for」ループを使用して配列を反復処理します。配列内の各要素について、それを「currentSum」に追加します。 「currentSum」が「maxSum」より大きい場合、「maxSum」を「currentSum」に更新し、「end」を現在のインデックスに設定します。

ステップ3

次に、while ループを使用して、「currentSum」が「0」より小さいかどうかを確認します。その場合、「currentSum」から「start」の値を減算し、「start」に 1 を加えます。これにより、配列の連続したサブセットが常に確保されます。

ステップ4

最後に、「currentSum」が「maxSum」と等しいかどうか、および現在のサブ配列のサイズが前のサブ配列よりも大きいかどうかを確認します。そうであれば、「end」を現在のインデックスに更新します。

ステップ5

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) で、これがこの問題にとって最適です。

＃＃＃例＃＃＃

次の JavaScript プログラムは、2 つのポインター (start と end) を使用して、整数配列内で最大の合計を持つ連続した部分配列を見つける問題を解決するように設計されています。このアルゴリズムは、最大合計を負の無限大に初期化し、現在の合計をゼロに、開始インデックスと終了インデックスをゼロに初期化します。現在の合計に各要素を追加し、現在の合計が最大合計より大きい場合は最大合計と終了インデックスを更新します。現在の合計が負でなくなるまで部分配列の先頭から要素を削除し、現在の合計が最大合計と等しく、部分配列の長さが前の部分配列の長さより大きい場合は、終了インデックスを更新します。最後に、終了インデックスから開始インデックスを減算し、1 を加算することで、最大の部分配列の長さを返します。

リーリー

理解を深めるために、いくつかの例を使用して出力を見てみましょう。

例 1

入力

- 整数配列の場合、a[]= {1, -2, 1, 1, -2, 1}

出力

−

2

説明

- 最大合計が {1, 1} の連続する要素を含む部分配列。したがって、長さは 2 になります。

例 2 入力 - すべての負の整数の配列を指定すると、a[]= {-2, -5, -8, -3, -1, -7}

出力-1

説明

- この場合、最大の部分配列は [-1] になり、合計は -1 になります。したがって、部分配列の長さは -1 になります。

＃＃＃結論は＃＃＃ プログラミングで配列を扱う場合、合計が最大となる部分配列のサイズはよくある質問です。この問題を解決するアルゴリズムには、配列を反復処理し、現在の合計とこれまでに確認された最大の合計を追跡することが含まれます。このアルゴリズムを JavaScript で実装すると、指定された整数配列の合計が最大となる部分配列のサイズを効率的に見つけるプログラムを作成できます。

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