Maximum Average Subarray I

643. Maximum Average Subarray I

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

意思是, 给一个长度为n的数组, 和一个值k, 求所有长度为k的字数组的最大平均值.

Example:

input: [1,12,-5,-6,50,3], k = 4
output: 12.75

这个例子里面, 长度为4的子串当中, 平均值最大的是 [12, -5, -6, 50]

##思路
这个题, 比较简单, 很直观的方法就是, 新建一个数组, 存累加的结果. 还是上面那个例子

nums = [1, 12, -5, -6, 50, 3]
sums = [1, 13, 8, 2, 52, 55]

有了这个累加的结果后, nums[0, 4]的和是sums[3], nums[1, 5]的和是sums[4] - sums[0]. 这样我们就有左右子串的和了. 那么求平均值就很容易了.

Code

def maxAverage(nums, k):
    sums = [0] * len(nums)
    s = 0
    for i in range(len(nums)):
        s += nums[i]
        sums[i] = s

    res = sums[k-1]/float(k)
    left = 0
    right = k
    while right < len(nums):
        tmp = sums[right] - sums[left]
        res = max(res, tmp/float(k))
        left += 1
        right += 1
    return res

时间复杂度

$O(n)$

EOF