K 사이즈 배열의 가장 큰 합 구하기

Maximum Sum Subarray of Size K (easy)

리트코드의 이지 난이도 문제 풀이다.

해당 범위의 가장 큰 합 구하기

시간 복잡도 : O(N)

공간 복잡도 : O(1) (배열 요소 없이 정수형 변수만 사용)

1. 루프 밖에 윈도우 시작 인덱스 0으로 초기화(window_start=0)
2. 길이 k가 되기 전엔 계속 더함
3. 길이 k가 되면 (window_end>=k-1)
   1. 최대값 계산
   2. 맨 앞 인덱스 값 빼줌
   3. 맨 앞 인덱스 증가

파이썬 해답

def max_sub_array_of_size_k(k, arr):
  max_sum , window_sum = 0, 0
  window_start = 0

  for window_end in range(len(arr)):
    window_sum += arr[window_end]  # 다음 요소 더함.
    # k 길이 전까지는 그냥 더한다.
    if window_end >= k-1:
      max_sum = max(max_sum, window_sum)
      window_sum -= arr[window_start]  # 나갈 요소 뺌
      window_start += 1  # 윈도우 인덱스 증가
  return max_sum