[Leetcode] 643. Maximum Average Subarray I (C++ 풀이)

 

integer array와 subarray의 길이를 나타내는 k가 인자로 주어졌을 때, array에서 길이 k의 subarray의 최대 평균 값을 반환하자. 슬라이딩 윈도우 기법으로 모든 subarray를 순차탐색하며 최대 평균(or 합)을 계산할 수 있다. 매번 subarray의 평균을 새롭게 계산하는 것이 아니라, 이전 subarray를 캐싱을 해서 연산을 최소화할 수 있다.

 

 

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double cur_sum = 0.0;
        double max_sum = 0.0;

        for (int i = 0; i < k; i++){
            cur_sum += nums[i];
        }

        max_sum = cur_sum;

        for(int i = k; i < nums.size(); i++){
            cur_sum = cur_sum - nums[i-k] + nums[i];

            if (cur_sum > max_sum)
                max_sum = cur_sum;
        }

        return max_sum / k;
    }
};

첫 루프에서 초기 subarray의 합을 계산한다. cur_sum은 sum of subarray가 될 것 이고, max_sum은 지금까지 계산된 최대 부분 합을 저장할 것이다. 

 

마지막에 반환할 때, k로 나눠줌으로써 평균을 쉽게 계산할 수 있겠다.

 

두번째 루프에서 보면, 다음 차례의 subarray를 계산할 때, 단순히 num[i-k] 값을 빼고, nums[i]를 더해줌으로써, 추가적인 loop없이 새로운 부분합을 계산할 수 있다.

 

runtime efficiency도 100%를 달성한 것을 볼 수 있다!