指定された配列のすべての回転の中から i*arr の最大合計を見つける JavaScript プログラム

この記事では、指定された配列のすべての回転の中で i*arr[i] の最大合計を見つける JavaScript プログラムを実装します。ここで、 i*arr[i] は、配列のすべての要素を現在の位置の要素と乗算して合計を最大化することを意味します。与えられた配列要素を左また​​は右に回転して、最大の答えを得ることができます。この質問に対して、完全なコードと詳細な説明を提供します。

問題の紹介

この質問では、配列が与えられています。すべての要素に対応するインデックス番号を乗算し、すべての要素の合計を加算すると、数値が得られます。 1 回の回転で、左端または右端の要素を配列の反対側に移動することができ、これにより各要素のインデックスが変更され、配列を何度でも回転させることができます (ただし、回転数が 2 に等しくなった場合)。配列の長さ、最初のものと同じ配列が得られます)、配列を回転することで要素のインデックス、つまり i*arr[i] の合計を変更できます。

2 つのアプローチで合計を最大化しようとします。まず、例を見てみましょう -

最初のローテーションで、最大の合計である 29 が得られていることがわかります。

必要な合計を見つけるには 2 つの方法があります。両方を見てみましょう -

方法 1 は素朴なアプローチです。配列のすべての回転を O(N) 時間で見つけ、各回転について、配列を走査することによって O(N) 時間ですべての要素の合計を見つけます。余分なスペースを使用します。

時間計算量と空間計算量

上記のコードの時間計算量は O(N*N) です。N は配列のサイズであり、上記のコードの空間計算量は O(1) です。

各反復では、最後の要素については 1 つの要素の差しかありません。これは、その要素の要素が配列の長さから 1 から 0 に更新され、他の要素については 1 つ以上の要素が追加されるためです。 −

時間計算量と空間計算量

上記のコードの時間計算量は O(N) です。N は配列のサイズで、上記のコードの空間計算量は O(1) です。このアプローチは、前のアプローチと比較して非常に優れています。

このチュートリアルでは、指定された配列のすべての回転の中で i*arr[i] の最大合計を見つける JavaScript プログラムを実装しました。 2 つの方法を見てきました。1 つは、指定された配列のすべての回転を検索し、それらの i*arr[i] 式の結果を比較するものです。 2 番目の方法では、数学的手法を使用して時間計算量を O(N*N) から O(N) に削減します。

以上が指定された配列のすべての回転の中から i*arr の最大合計を見つける JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。