[Leetcode] 643 Maximum Average Subarray I (Python)

문제

Maximum Average Subarray I - LeetCode

설명

You are given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

풀이 계획

배열을 n-k만큼 돌면서 모든 경우의 최대합 값을 비교하여 구한다. 마지막까지 돌고 반복문을 나와서 최대합 값을 k로 나눈 값을 리턴하면 될 것으로 생각했다. 배열의 길이가 1인 경우 반복문 범위 처리를 하지 않고 바로 해당 값/k 를 리턴하도록 했다.

초기 풀이

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_val = 0
        if len(nums)==1:
            return nums[0]/k
        for i in range(len(nums)-k+1):
            if sum(nums[i:i+k]) > max_val:
                max_val = sum(nums[i:i+k])
            print(max_val)
        return max_val/k

문제점 및 해결 방안

일단 배열에 최소값이 -10의4제곱이었기 때문에 최대합 값을 0으로 설정하면 안됐다. 0으로 할 경우 모든 연속된 k만큼의 부분합이 0보다 작다면 결과가 0으로 남아서 틀린 결과가 된다. 배열 가장 앞 부분합을 window_sum으로 두고 그 부분을 초기에 최대합을 나타내는 max_sum으로 잡는다. 이후 k부터 nums길이만큼 반복문을 돌면서 다음 값을 더해주고 이전 값을 빼주는 식으로 하나하나 진행해주고 매 순간 max_sum값과 비교하여 최대합을 구한다.

고친 풀이

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = sum(nums[:k])
        max_sum = window_sum
        for i in range(k, len(nums)):
            window_sum += nums[i] - nums[i-k]
            if window_sum > max_sum:
                max_sum = window_sum
        return max_sum/k

복잡도

시간복잡도 : O(N)
공간복잡도 : O(1)