。重疊子數組的最大和

689。 3 個不重疊子數組的最大和

難度：難

主題：數組，動態規劃

給定一個整數數組 nums 和一個整數 k，找到三個長度為 k 且總和最大的不重疊子數組並傳回它們。

傳回結果作為表示每個間隔起始位置的索引清單（0-索引）。如果有多個答案，則傳回字典順序最小的一個。

範例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 4
• 1 16
• 1

解：

我們將使用動態規劃法。這個想法是將問題分解為更小的子問題，利用子數組的重疊來有效計算長度為 k 的三個非重疊子數組的最大和。

方法：

1. 預先計算長度為 k 的子數組的總和：
   首先，我們計算輸入數組 nums 中所有長度為 k 的子數組的總和。透過使用滑動視窗技術，可以在線性時間內有效地完成此操作。

2. 動態規劃（DP）：
   我們建立兩個輔助數組（左數組和右數組）來儲存截至目前位置找到的最佳子數組的索引。 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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。重疊子數組的最大和的詳細內容。更多資訊請關注PHP中文網其他相關文章！