Maximum Sum Subarray of Size K

Q: 고정 크기 슬라이딩 윈도우란 무엇인가요?

배열을 가로질러 한 번에 한 단계씩 이동하는 정확히 k 개의 인접한 요소로 이루어진 범위입니다. 각 위치에서 범위를 처음부터 다시 계산하는 대신, 누적 값을 업데이트합니다. 오른쪽에서 새로 들어오는 요소를 더하고 왼쪽에서 빠져나가는 요소를 제거합니다. 이렇게 하면 작업량이 O(n·k) 에서 O(n) 으로 줄어듭니다.

Q: 크기가 k인 최대 합 부분 배열의 시간 복잡도는 얼마인가요?

슬라이딩 윈도우를 사용하면 시간 복잡도는 O(n) 이고 추가 공간 복잡도는 O(1) 입니다. 첫 번째 윈도우의 합을 구하기 위해 한 번 순회한 다음, 각 단계에서 한 번 더하고 한 번 뺍니다. 각 윈도우의 합을 별도로 구하면 (n-k+1) × k 번의 덧셈이 필요하며, 이는 O(n·k) 입니다. n = 10^4 이고 k = 5000 일 때 약 2.5 × 10^7 입니다.

Q: 이것은 최대 부분 배열 문제와 어떻게 다른가요?

여기서는 길이가 k 로 고정되어 있으므로 모든 후보가 윈도우이며, 슬라이딩 합으로 모든 후보를 살펴볼 수 있습니다. 최대 부분 배열 문제에서는 길이가 정해져 있지 않으므로, 각 원소에서 현재 구간을 확장할지 새 구간을 시작할지 결정하는 Kadane 알고리즘이 필요합니다. 고정 윈도우에는 그런 선택지가 없습니다.

쉬움슬라이딩 윈도우

+10

정수 배열 nums와 윈도우 길이 k가 주어집니다. 서로 이웃한 원소가 정확히 k개인 모든 구간을 살펴보고, 그중 합이 가장 큰 값을 반환하세요. 값은 음수일 수 있으므로 답도 음수일 수 있습니다.

함수

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: 정수 배열
kinteger: 각 윈도우가 보유하는 이웃 요소의 수
반환값integer: 연속된 k개 요소의 합 중 최댓값

제약 조건

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

예제

입력: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
출력: 10
설명: 길이가 3인 다섯 개의 윈도우의 합은 6, 9, 8, 10, 4입니다. 가장 큰 값은 7 + (-2) + 5 = 10입니다.

입력: nums = [-3, -8, -1, -6]k = 2
출력: -7
설명: 모든 값이 음수이므로 모든 윈도우 합도 음수입니다: -11, -9, -7. 그중 가장 큰 값은 -1 + (-6) = -7입니다.

입력: nums = [5, -2, 4]k = 3
출력: 7
설명: k가 배열의 길이와 같으면 윈도우는 하나이며, 배열 전체가 윈도우이고 5 + (-2) + 4 = 7입니다.

후속 질문

최적의 윈도우가 시작되는 위치도 반환할 수 있나요? 여러 윈도우의 결과가 같으면 가장 왼쪽에 있는 윈도우를 선택하세요.

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

n-k+1개의 윈도우가 있으며, 각 윈도우를 처음부터 모두 더하는 데는 k번의 덧셈이 필요합니다. 핵심은 이웃한 두 윈도우가 원소 두 개를 제외하고 모두 겹친다는 점입니다. 윈도우를 새로 만드는 대신 밀어 이동하세요. 값 하나가 들어오고 하나가 나가므로, 각 윈도우의 합을 구하는 데 두 번의 연산만 필요합니다.

모든 창을 합산하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

윈도우는 시작 위치로 결정됩니다. 인덱스 0, 1 등에서 시작할 수 있으며, n-k까지 가능합니다. 그보다 뒤에서 시작하면 배열의 끝을 넘어가기 때문입니다. 각 시작 위치에서 k개의 요소를 더하고, 그 합을 지금까지의 최댓값과 비교합니다.

[4, -1, 3, 7, -2, 5, 1]과 k = 3의 경우 합은 6, 9, 8, 10, 4가 되며, 답은 10입니다. 최댓값은 첫 번째 윈도우의 합이나 가장 작은 정수로 시작해야 하며, 0으로 시작하면 안 됩니다. 모든 값이 음수라면 0이 실제 윈도우의 모든 합보다 커지기 때문입니다.

연산 비용은 (n-k+1) × k번의 덧셈입니다. k가 n의 절반 정도일 때 비용이 가장 큽니다. n = 10^4이고 k = 5000이면 5001 × 5000번, 즉 약 2.5 × 10^7번의 덧셈이 필요하며, 그중 거의 전부는 바로 앞 윈도우에서 수행한 작업을 반복합니다.

알고리즘

best를 가능한 가장 작은 값으로 설정합니다.
0부터 n-k까지 각 시작 위치에 대해 total = 0으로 설정합니다.
nums[start]부터 nums[start+k-1]까지의 값을 total에 더합니다.
total이 best보다 크면, 그 값을 저장합니다.
best를 반환합니다.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

고정된 윈도우를 이동하세요

핵심 아이디어

인덱스 0에서 시작하는 윈도우와 인덱스 1에서 시작하는 윈도우를 비교해 보세요. k = 3인 [4, -1, 3, 7, -2, 5, 1]에서 두 윈도우의 합은 각각 4 + (-1) + 3 = 6과 (-1) + 3 + 7 = 9입니다. 둘 다 -1과 3을 포함합니다. 두 번째 합은 첫 번째 합에 새로 들어온 값 7을 더하고, 빠져나간 값 4를 뺀 값입니다. 즉, 6 + 7 - 4 = 9입니다.

이 방식은 모든 단계에서 성립합니다. 윈도우의 오른쪽 끝이 인덱스 i로 이동하면, i의 요소가 들어오고 i-k의 요소가 빠져나갑니다. 따라서 첫 번째 윈도우의 합을 한 번 구한 다음, 각 단계에서 한 번의 덧셈과 한 번의 뺄셈으로 합을 갱신합니다. 합은 브루트 포스 방식과 동일하게 6, 9, 8, 10, 4가 되며, 이 중 최댓값을 유지합니다.

각 요소는 한 번 들어오고 최대 한 번 빠져나가므로 시간 복잡도는 O(n)입니다. 현재 윈도우의 합과 최댓값, 두 개의 숫자만 유지하므로 추가 공간 복잡도는 O(1)입니다. 여기서 어떤 합도 10^4 × 10^4 = 10^8을 넘지 않으므로 32비트 정수면 충분합니다.

알고리즘

nums[0]부터 nums[k-1]까지 더해 window에 저장합니다.
best = window로 설정합니다.
k부터 n-1까지 모든 i에 대해 nums[i]를 더하고 nums[i-k]를 뺍니다.
각 단계가 끝날 때마다 best를 best와 window 중 더 큰 값으로 설정합니다.
best를 반환합니다.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

함정과 경계 사례

윈도우 아이디어는 간단하므로, 버그는 시작값과 인덱스에 숨어 있습니다.

best를 0으로 시작하기. [-3, -8, -1, -6]와 k = 2에서는 실제 답이 -7이지만, best가 0이면 이를 이기는 값이 없어서 답으로 반환됩니다.
잘못된 요소를 빼기. nums[i]가 들어올 때 나가는 요소는 nums[i-k]입니다. nums[i-k+1] 또는 nums[i-k-1]을 사용하면 윈도우 길이가 잘못됩니다.
완전 탐색을 시작 위치 하나 전에 멈추기. 마지막 윈도우는 n-k에서 시작하므로, 반복문에서 이 위치를 포함해야 합니다. k = n이면 이 윈도우가 유일한 윈도우이며, 인덱스를 하나 빼먹으면 윈도우를 확인하지 않고 best의 시작값을 반환합니다.
반복문이 끝난 뒤에만 비교하기. 최적의 윈도우가 첫 번째 윈도우일 수 있으므로 첫 번째 합도 비교하거나, 그 값으로 best를 초기화해야 합니다.
R과 Lua는 1부터 세는 것을 잊기. 첫 번째 윈도우는 nums[1..k]이며, nums[i]가 들어올 때 나가는 요소는 여전히 nums[i-k]입니다.

자주 묻는 질문3

고정 크기 슬라이딩 윈도우란 무엇인가요?

배열을 가로질러 한 번에 한 단계씩 이동하는 정확히 k개의 인접한 요소로 이루어진 범위입니다. 각 위치에서 범위를 처음부터 다시 계산하는 대신, 누적 값을 업데이트합니다. 오른쪽에서 새로 들어오는 요소를 더하고 왼쪽에서 빠져나가는 요소를 제거합니다. 이렇게 하면 작업량이 O(n·k)에서 O(n)으로 줄어듭니다.

크기가 k인 최대 합 부분 배열의 시간 복잡도는 얼마인가요?

슬라이딩 윈도우를 사용하면 시간 복잡도는 O(n)이고 추가 공간 복잡도는 O(1)입니다. 첫 번째 윈도우의 합을 구하기 위해 한 번 순회한 다음, 각 단계에서 한 번 더하고 한 번 뺍니다. 각 윈도우의 합을 별도로 구하면 (n-k+1) × k번의 덧셈이 필요하며, 이는 O(n·k)입니다. n = 10^4이고 k = 5000일 때 약 2.5 × 10^7입니다.

이것은 최대 부분 배열 문제와 어떻게 다른가요?

여기서는 길이가 k로 고정되어 있으므로 모든 후보가 윈도우이며, 슬라이딩 합으로 모든 후보를 살펴볼 수 있습니다. 최대 부분 배열 문제에서는 길이가 정해져 있지 않으므로, 각 원소에서 현재 구간을 확장할지 새 구간을 시작할지 결정하는 Kadane 알고리즘이 필요합니다. 고정 윈도우에는 그런 선택지가 없습니다.

def maxSumSubarray(nums, k):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

예상 출력