arrays - 找到使数组其余部分的平均值最小化的连续子序列？

Question

假设有一个整数数组arr[0..n-1]。找到一个子序列sub[i..j]（i > 0 和 j < n - 1），使得数组的其余部分具有最小的平均值。

例子：

arr[5] = {5,1,7,8,2};

移除{7,8}，数组变为{5, 1, 2}平均为 2.67（尽可能小）。

我认为这是对最长增加子序列的修改，但无法弄清楚。

谢谢，

Answer 1

让我们使用二进制搜索找到平均值。

假设所有元素的总和为 S。

对于给定的 x，让我们检查是否存在 i 和 j，使得除了从 i 到 j 之外的所有元素的平均值小于或等于 x。

为此，让我们从 arr 中的所有元素中减去 x。我们需要检查是否存在 i 和 j 使得除了 i 到 j 之外的所有元素的总和小于或等于零。为此，让我们找到当前数组中所有元素的总和：S' = S - x * n。所以我们想找到 i 和 j 使得 i 到 j 的总和大于或等于 S'。为此，让我们找到最大和的子数组。这可以使用优雅的 Jay Kadane 算法来完成：https ://en.wikipedia.org/wiki/Maximum_subarray_problem

何时终止二分查找？当最大子数组总和为零（或足够接近）时。

时间复杂度：O(n log w), w - 二分查找的精度。