arrays - 寻找连续的子序列以使其余阵列的平均值最小？

假设有一个整数数组arr[0..n-1]找到一个子序列sub[i..j]（i>0和j例子：

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

移除{7,8}，数组变为{5, 1, 2}，平均值为2.67（可能最小）。
我以为这是对最长递增子序列的修改，但没搞清楚。
谢谢，

最佳答案

让我们使用二进制搜索查找平均值。
假设，所有元素的和是s。
对于给定的x，让我们检查是否存在i和j，使得除i到j以外的所有元素的AVG小于或等于x。
为了做到这一点，让我们从AR中的所有元素减去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 -二元搜索的假设。

关于arrays - 寻找连续的子序列以使其余阵列的平均值最小？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34834082/