查找子数组的元素的最大金额/数量 [英] Finding subarray with maximum sum/number of elements

问题描述

输入：n个正数和负数和一个数k的数组

Input: An array of n positive and negative numbers and a number k.

输出：子阵至少k个连续元素与元素在子阵元数除以最大总和

Output: Subarray of at least k consecutive elements with maximum sum of elements divided by number of elements in the subarray.

为O（n ^ 2）算法很容易。有没有人有一个更好的算法吗？

O(n^2) algorithm is easy. Does anyone have a better algorithm for this?

推荐答案

您可以使用二进制搜索。

You can use binary search.

有关搜索的值 X ，考虑阵列 B [I] = A [1] - X 。现在找到长度的最大总和子数组至少 K 。

For a searched value x, consider the array b[i] = a[i] - x. Now find the maximum sum subarray of length at least k.

这工作，因为长度 K 的子数组的平均值为（一[P] + ... +一[P + K - 1）/ K 。因此，我们有：

This works because the average of a subarray of length k is (a[p] + ... + a[p + k - 1]) / k. So we have:

(a[p] + ... + a[p + k - 1]) / k >= avg
a[p] + ... + a[p + k - 1] >= avg * k
(a[p] - avg) + ... + (a[p + k - 1] - avg) >= 0

所以，如果你的二进制搜索的平均值，由每个元素减去它，如果你能找到一个正和子阵列（找出最大的一个，检查它是否阳性）长度至少氏/ code>，然后平均是一个有效的答案：继续在搜索[AVG，max_avg] 看你是否能找到一个更好的。如果没有，降低搜索 [0，平均] 。

So, if you binary search for the average, by substracting it from each element, if you can find a positive-sum subarray (find the maximum one and check if it's positive) of length at least k, then avg is a valid answer: continue to search in [avg, max_avg] to see if you can find a better one. If not, reduce search to [0, avg].

这篇关于查找子数组的元素的最大金额/数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！