回転された配列内の指定された長さの連続した部分配列の最大合計を見つけるクエリ用の JavaScript プログラム

配列を回転すると、数値が取得され、配列の要素を循環順序で右または左に移動する必要があります。ここでは指定していないため、右回転を基準として使用し、指定された回転数の後、最大の合計を持つ部分配列を返します。記事内で正しい説明付きのコードを見ていきます。

問題の紹介

この問題では、整数を含む配列とクエリ ペアを含む別の配列を取得します。クエリ配列の各インデックスには 2 つの整数が含まれており、最初の整数は現在の配列の回転数を表し、2 番目の整数は目的のサブ配列の長さを表します。例えば ​​-＃＃＃

指定された配列が [5, 7, 1, 4, 3, 8, 2] で、クエリが次の場合 -

リーリー

この問題の解決策に移りましょう

単純な方法

最も簡単な方法は、2 つの for ループを直接使用して、指定された問題を実装することです。まず、配列上を移動し、指定された回数だけ時計回りに回転させます。次に、指定されたサイズのサブ配列と最大の合計を持つサブ配列を見つけます。コードを見てみましょう -

＃＃＃例＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(Q*D*N) です。ここで、Q はクエリの数です。 D は必要な各サブ配列のサイズ、N は配列の長さです。

回転された配列を格納するために追加の配列を使用するため、上記のコードの空間計算量は O(N) です。

効率的な方法

スライディング ウィンドウ方式を使用すると、この問題を効果的に解決できます。この質問のコードに直接アクセスして、概要を理解しましょう -

＃＃＃例＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(Q*N) です。ここで、Q はクエリの数、N は配列の長さです。

回転された配列を格納するために追加の配列を使用するため、上記のコードの空間計算量は O(N) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、回転された配列内の指定された長さの連続した部分配列の最大合計を見つけるクエリを実行するための JavaScript プログラムを実装しました。時間計算量 O(N*Q*D) の単純なメソッドを実装し、スライディング ウィンドウの概念を使用してそれを O(N*Q) 時間計算量に改善しましたが、両方のコードの空間計算量は同じ O(N) でした。

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