。重叠子数组的最大和

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中文网其他相关文章！