。重複するサブ配列の最大合計

689。 3 つの重複しないサブ配列の最大合計

難易度: 難しい

トピック: 配列、動的プログラミング

整数配列 nums と整数 k を指定すると、合計が最大となる長さ k の重複しない部分配列を 3 つ見つけて返します。

結果を各間隔の開始位置を表すインデックスのリストとして返します (0-indexed)。複数の答えがある場合は、辞書順に最小のものを返します。

例 1:

• 入力: nums = [1,2,1,2,6,7,5,1]、k = 2
• 出力: [0,3,5]
• 説明: サブ配列 [1, 2]、[2, 6]、[7, 5] は開始インデックス [0, 3, 5] に対応します。
  • [2, 1] を選択することもできますが、[1, 3, 5] の答えは辞書編集的に大きくなります。

例 2:

• 入力: nums = [1,2,1,2,1,2,1,2,1]、k = 2
• 出力: [0,2,4]

制約:

• 1 2 * 104
• ^{1 16}
1

解決策:

動的プログラミングのアプローチを使用します。このアイデアは、問題をより小さな部分問題に分割し、部分配列の重複を利用して、長さ k の重複しない 3 つの部分配列の最大合計を効率的に計算することです。
アプローチ：

1. 長さ k の部分配列の合計を事前計算します:
   

   まず、入力配列 nums 内の長さ k のすべての部分配列の合計を計算します。これは、スライディング ウィンドウ手法を使用すると、線形時間で効率的に実行できます。

2. 動的プログラミング (DP):
   

   現在の位置までに見つかった最良の部分配列のインデックスを保存するために、左右の 2 つの補助配列を作成します。 left[i] にはインデックス i より前で終わる最適なサブ配列のインデックスが格納され、right[i] にはインデックス i より後に始まる最適なサブ配列のインデックスが格納されます。

3. 最大合計を反復して計算します:
   

   インデックス j から始まる考えられる中央のサブ配列ごとに、j の前の最良の左サブ配列と j の後の最良の右サブ配列を考慮して合計を計算します。

4. 辞書順:
   

   複数の有効な回答 (合計が同じ) がある場合は、辞書編集的に最小のものを返します。これは反復順序によって保証されます。

このソリューションを PHP で実装してみましょう: 689。 3 つの重複しないサブ配列の最大合計

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function maxSumOfThreeSubarrays($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5]
print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4]
?>

説明：

1. サブ配列の合計の計算:

   • 長さ k のすべての可能な部分配列の合計を計算します。これは、最初に最初の k 要素の合計を計算することによって行われます。次に、後続の各位置について、残った要素を減算し、配列内の次の要素を追加することで、効率的なスライディング ウィンドウ アプローチとなります。

2. 左右の配列:

   • left[i] は、インデックス i の前で終わる最大合計を持つ部分配列のインデックスを保持します。
   • right[i] は、インデックス i の後に始まる最大合計を持つ部分配列のインデックスを保持します。

3. 最終計算:

   • 中央の各サブ配列 j について、最良の左サブ配列と最良の右サブ配列の組み合わせをチェックし、合計が現在の最大値より大きい場合は結果を更新します。

4. 辞書編集的に最小の答え:

   • 左から右に反復すると、最大の合計を生成する最初の部分配列が自然に選択されるため、辞書編集的に最小の解が得られます。

例：

入力用:

$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;

出力は次のようになります:

[0, 3, 5]

このアプローチにより、時間計算量が効率的に維持され、時間計算量は約 O(n) になります。ここで、n は入力配列 nums の長さです。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

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