FilesExpand file tree

 master

/

maximum-average-subarray-i.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

27 lines (25 loc) · 793 Bytes

 master

/

maximum-average-subarray-i.py

Copy path

Top

File metadata and controls

• Code
• Blame

27 lines (25 loc) · 793 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# Time: O(n)

# Space: O(1)

# 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

# Note:

# 1 <= k <= n <= 30,000.

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

class Solution(object):

def findMaxAverage(self, nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: float

"""

result = total = sum(nums[:k])

for i in xrange(k, len(nums)):

total += nums[i] - nums[i-k]

result = max(result, total)

return float(result) / k