LeetCode/Array/findMaxAverage.py at master · konantian/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
'''
Source : https://leetcode.com/problems/maximum-average-subarray-i/
Author : Yuan Wang
Date   : 2018-06-12

/***************************************************************************************
*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 = 4
*Output: 12.75
*Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

 ****************************************************************************************
 '''
#Time complexity: O(n), Space complexity:O(1)
def findMaxAverage(nums, k):
	"""
	:type nums: List[int]
	:type k: int
	:rtype: float
	"""
	if len(nums) == k:
		return sum(nums)/k

	first=0
	temp=total=sum(nums[:k])
	for i in range(k,len(nums)):
		temp=temp-nums[first]+nums[i]
		total = temp if temp > total else total
		first+=1
	return total/k

nums=[1,12,-5,-6,50,3]
k=4
print(findMaxAverage(nums,k))