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. 1 <= k <= n <= 30,000.

2. Elements of the given array will be in the range [-10,000, 10,000].

 题意：求一个数组的最大子阵列平均数

 思路：运用动态规划，找出和最大、长度为k的子阵列

1. class Solution(object):
2. def findMaxAverage(self, nums, k):
3. """
4. :type nums: List[int]
5. :type k: int
6. :rtype: float
7. """
8. sum = 0
9. curSum = 0
10. addNum = 0
11. for i in range(0, len(nums)):
12. if addNum < k:
13. curSum += nums[i]
14. sum = curSum
15. addNum += 1
16. else:
17. curSum = curSum - nums[i - k] + nums[i]
18. sum = max(sum, curSum)
19. return sum * 1.0 / k