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.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4Output: 12.75Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].
题意：求一个数组的最大子阵列平均数
思路：运用动态规划，找出和最大，长度为k的子阵列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution(object): def findMaxAverage(self, nums, k): """ :type nums: List[int] :type k: int :rtype: float """ sum = 0 curSum = 0 addNum = 0 for i in range(0, len(nums)): if addNum < k: curSum += nums[i] sum = curSum addNum += 1 else: curSum = curSum - nums[i - k] + nums[i] sum = max(sum, curSum) return sum * 1.0 / k |
643. Maximum Average Subarray I 最大子阵列平均数
原文：http://www.cnblogs.com/xiejunzhao/p/7191297.html