[643] Maximum Average Subarray I
https://leetcode.com/problems/maximum-average-subarray-i/description/
- algorithms
- Easy (38.22%)
- Source Code: 643.maximum-average-subarray-i.py
- Total Accepted: 49K
- Total Submissions: 124.8K
- Testcase Example: '[1,12,-5,-6,50,3]\n4'
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].
python
class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
lenn = len(nums)
if lenn < k: return 0
sm = -0xffffffff
for i in range(lenn-k+1):
if i+1+k < lenn and nums[i] < nums[i+1+k]: continue
out = sum(nums[i:i+k])
if out > sm:
sm = out
return 1.0 * sm / k
# 这个测试用例通过不了。。。
# nums = [64,514,188,145,614,214,888,344,380,781,346,668,165,687,236,551,338,609,401,118,662,911,907,792,83,942,213,427,442,979,700,507,493,888,4,107,454,893,803,834,26,150,502,191,189,738,742,528,699,496,998,361,407,257,154,842,551,719,270,994,699,970,853,544,210,209,652,665,102,807,499,480,957,354,672,499,92,766,27,792,614,377,505,373,986,11,216,889,731,838,883,782,160,88,326,370,298,330,35,752,138,887,233,447,241,257,946,685,23,325,829,638,54,335,11,392,346,579,282,429,417,165,211,577,606,890,300,904,572,335,656,710,222,889,510,815,498,808,501,522,486,330,512,540,665,875,933,364,455,567,793,224,732,357,154,690,599,454,594,171,141,603,234,716,844,744,531,343,904,32,865,390,715,729,931,380,604,216,96,411,783,890,636,867,599,790,558,198,596,504,369,737,107,603,805,952,699,337,295,604,721,512,994,436,241,277,169,197,845,265,609,628,507,245,848,106,387,758,656,335,262,26,72,370,981,230,674,681,567,969,637,640,833,983,429,426,261,598,623,106,215,232,87,723,829,935,181,568,693,838,903,307,216,328,677,197,558,703,230,477,24,219,469,857,203,898,283,464,848,259,922,64,843,9,139,673,296,320,593,341,510,849,649,726,177,678,276,87,382,858,916,758,78,385,616,281,284,251,97,132,862,371,548,706,733,687,379,29,360,324,723,870,173,372,949,702,402,225,141,136,83,57,895,513,443,863,794,79,466,243,211,329,615,112,35,700,799,766,729,159,90,452,382,616,176,331,318,579,908,812,67,343,869,962,857,664,825,3,743,292,247,307,621,214,419,656,914,570,422,995,82,864,800,464,480,328,147,151,259,407,315,327,750,184,641,607,201,467,611,944,111,210,603,84,776,374,92,42,945,866,389,379,730,541,195,563,870,694,66,481,101,381,808,851,917,450,811,118,269,774,415,732,336,370,816,112,745,908,506,42,126,247,773,208,789,968,771,11,662,189,492,763,922,301,966,840,103,777,310,372,551,77,104,887,448,272,351,545,532,209,939,658,457,712,866,246,32,990,257,694,531,749,809,454,402,127,646,505,905,956,229,808,386,685,696,834,957,399,731,841,609,670,499,66,734,718,664,766,60,273,812,591,22,621,45,425,100,691,282,5,0,512,814,386,197,862,572,507,613,303,348,574,325,200,992,59,918,656,825,978,929,637,921,304,610,967,81,710,10,363,68,362,227,234,748,777,448,672,284,61,975,984,636,300,184,628,711,102,637,536,432,918,525,354,222,135,673,303,198,35,19,618,398,598,852,498,375,300,171,11,713,498,996,701,151,180,682,862,635,671,751,419,589,276,125,812,764,150,467,962,186,838,580,936,437,784,434,164,84,957,176,149,456,172,203,959,704,885,821,691,556,572,111,145,201,588,309,965,739,129,279,925,967,859,213,756,995,999,921,79,957,97,580,765,621,783,724,325,668,897,17,576,822,480,74,23,68,383,988,807,512,267,84,832,478,297,588,473,297,509,904,606,958,484,723,579,620,799,905,640,48,274,217,870,754,643,893,174,26,233,982,891,852,418,75,330,716,663,155,365,525,59,323,483,896,46,63,868,845,320,508,245,594,77,116,700,720,361,874,99,947,208,990,799,627,65,482,695,80,637,60,605,49,735,89,297,781,152,165,978,824,25,223,770,103,691,470,823,53,696,922,352,905,264,151,884,681,985,579,762,975,991,367,376,726,808,673,859,960,190,837,136,215,412,906,318,456,728,494,861,425,416,213,682,681,364,566,362,702,145,476,677,136,844,53,214,652,78,73,965,268,262,101,835,674,360,154,130,88,0,991,865,416,556,547,449,273,465,164,975,962,640,652,450,484,57,664,489,135,737,806,755,999,259,590,26,619,96,508,60,96,852,925,865,408,825,314,681,290,478,656,605,471,660,55,307,717,72,796,204,161,954,311,161,566,254,539,185,702,47,597,799,251,523,16,660,700,682,693,990,513,702,947,984,362,3,291,432,75,440,988,236,394,300,749,312,554,640,850,256,40,447,407,291,322,775,303,22,458,997,365,971,699,312,307,413,315,598,197,742,390,186,331,137,838,432,449,744,73,299,352,113,747,112,404,69,887,60,444,697,57,809,668,108,121,975,873,789,926,71,883,316,609,214,453,799,999,903,895,72,202,247,537,301,711,293,723,599,353,167,648,410,976,669,870,449,996,744,238,922,167,122,591,776,688,44,927,687,299,822,111,854,69,648,155,133,294,230,732,647]
# k = 398
#
# ✘ answer: 517.51256
# ✘ expected_answer: 517.60553