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

Question

假设有一个整数数组arr[0..n-1]。找到一个子序列 sub[i..j] (i > 0 and 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 - 二分查找的精度。