질문을 뒤집을 때까지 Max Sum Min-Product를 최적화하지 못했다
Source: Dev.to
나를 곤란하게 만든 문제
LeetCode 1856 – Maximum Subarray Min‑Product
어떤 부분 배열이든 최소 원소에 그 부분 배열의 합을 곱한다.
모든 가능한 부분 배열 중에서 최대 값을 찾는다.
나는 O(n²) 풀이를 명확히 떠올릴 수 있었다: 모든 부분 배열을 시도하고, 현재 최소값과 현재 합을 유지하며, 최대값을 갱신한다. O(n) 로 줄이는 방법은? 바로 그 부분에서 막혔다.
직관이 틀린 이유
첫 번째 직감은 슬라이딩‑윈도우 접근법이었습니다: 범위에 요소를 추가하고, 답이 개선되는지 확인하고, 그렇지 않으면 최대값을 저장하고 초기화합니다. 범위를 만들고 확인하는 것이기 때문에 맞는 것처럼 느껴졌습니다.
왜 실패하는가: “계속 진행할지 초기화할지” 결정은 합계와 최소값이 동시에 변하는 두 가지에 모두 의존합니다.
- 큰 수를 추가하면 합계에는 도움이 되지만 최소값이 낮게 유지되면 도움이 되지 않을 수 있습니다.
- 작은 수를 추가하면 최소값이 낮아지고, 합계가 이를 보상할지 아직 알 수 없습니다.
검증할 깔끔한 탐욕적 조건이 없어서 잘못된 질문을 하고 있었습니다.
클릭을 만든 재구성
“최적의 구간은 무엇인가?” 라고 묻는 대신, 이렇게 바꿔보세요:
각 요소마다, 그 요소가 최소가 되는 가장 넓은 부분 배열은 무엇인가?
왜 이것이 모든 가능한 답을 포괄할까요? 최적의 부분 배열은 언제나 최소 요소를 가지고 있으며, 그 최소 요소는 배열 안의 값 중 하나이기 때문입니다. 각 요소를 잠재적 최소값으로 검토하고 그에 대한 최적의 부분 배열을 찾으면 답을 반드시 찾을 수 있습니다.
이렇게 하면 문제를 “모든 부분 배열을 탐색”하는 것에서 “각 요소마다 그 경계를 찾는” 것으로 바뀝니다. 이러한 경계를 찾는 것이 바로 단조 스택이 하는 일입니다.
단조 스택이 경계를 찾는 방법
- 인덱스 스택을 유지합니다. 스택에 저장된 값들은 아래에서 위로 엄격히 증가합니다.
- 배열을 순회하면서 현재 값이 스택 최상단 값보다 ≤ 작으면 스택을 팝합니다.
요소가 팝될 때 마법이 일어납니다:
| 경계 | 결정 방법 |
|---|---|
| 오른쪽 | 현재 요소(팝을 일으킨 요소)입니다. 이 요소가 더 작으므로 팝된 요소는 이 지점 이후에서는 최소가 될 수 없습니다. |
| 왼쪽 | 팝 후 새로 스택 최상단에 있는 요소(스택이 비었을 경우 -1). 이는 왼쪽에서 가장 가까운 작은 요소입니다. |
팝된 요소가 최소가 되는 부분 배열은 left_boundary + 1부터 right_boundary – 1까지입니다.
[3, 1, 6, 4, 5, 2]에 대한 추적
| i | 값 | 동작 | 스택 (인덱스) | 팝된 요소 | 왼쪽 | 오른쪽 | 부분 배열 (인덱스) |
|---|---|---|---|---|---|---|---|
| 0 | 3 | push | [0] | – | – | – | – |
| 1 | 1 | pop 0, push 1 | [1] | 3 | -1 | 1 | [0..0] |
| 2 | 6 | push | [1,2] | – | – | – | – |
| 3 | 4 | pop 2, push 3 | [1,3] | 6 | 1 | 3 | [2..2] |
| 4 | 5 | push | [1,3,4] | – | – | – | – |
| 5 | 2 | pop 4 → pop 3, push 5 | [1,5] | 5 | 3 | 5 | [4..4] |
| pop 1 (after loop) | [] | 1 | -1 | 6 | [0..5] |
스택이 팝 후 비게 되면 왼쪽 경계는 -1이 됩니다(“왼쪽에 더 작은 요소가 없으므로 인덱스 0까지 확장”). 모든 요소를 처리한 뒤 스택에 남아 있는 인덱스들은 오른쪽 경계가 없으며, 배열의 끝까지(right = n) 확장됩니다.
구간 합을 위한 O(1) 접두사 합
각 요소의 경계를 확보한 후, 해당 부분 배열의 합이 필요합니다. 앞에 0을 포함한 접두사 합 배열을 만드세요:
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
# sum of nums[a..b] = prefix[b + 1] - prefix[a]앞에 0을 넣으면 인덱스 0에서 시작하는 부분 배열에 대한 특수 케이스 처리를 피할 수 있고, 오프‑바이‑원 버그를 방지할 수 있습니다(제가 직접 힘들게 배운 교훈입니다).
전체 솔루션
def maxSumMinProduct(self, nums):
# 1️⃣ Prefix sums
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
result = 0
stack = [] # monotonic increasing stack of indices
# 2️⃣ Scan left → right
for i in range(len(nums)):
while stack and nums[stack[-1]] >= nums[i]:
popped = stack.pop()
left = stack[-1] if stack else -1
right = i
total = prefix[right] - prefix[left + 1]
result = max(result, nums[popped] * total)
stack.append(i)
# 3️⃣ Drain remaining elements (no right boundary)
while stack:
popped = stack.pop()
left = stack[-1] if stack else -1
right = len(nums)
total = prefix[right] - prefix[left + 1]
result = max(result, nums[popped] * total)
return result % (10**9 + 7)실제로 내가 저지른 실수
| 실수 | 알고리즘이 깨진 이유 |
|---|---|
while 조건에서 > 대신 >= 사용 | 같은 값의 요소가 팝되지 않아, 이후 중복 요소가 잘못된 왼쪽 경계를 계산하게 되었다. |
인덱스를 값으로 사용 (result = max(result, popped * total)) | 인덱스는 단순히 위치일 뿐이며, 해당 위치의 값 (nums[popped])을 사용해야 한다. |
leading zero 없이 prefix sum 사용 | 인덱스 0에서 시작하는 부분 배열에 대해 특수 케이스 처리가 필요했으며, 이로 인해 오프‑바이‑원 오류가 발생했다. |
이 세 가지 버그를 수정하면 버그가 있던 O(n²) 시도가 깔끔한 O(n) 솔루션으로 바뀐다.
pref_arr[0] = nums[0]은 인덱스 0부터 시작하는 합을 구하는 공식을 특수 케이스로 만들었다. 앞에 0을 추가하면 모든 구간이 동일한 공식prefix[right] - prefix[left + 1]을 사용한다.
다음에 연습할 내용
아래 모든 문제는 단조 스택을 이용한 “각 요소마다 경계를 찾는다” 패턴을 사용합니다.
| 문제 | LeetCode 번호 | 연습 내용 |
|---|---|---|
| 히스토그램에서 가장 큰 직사각형 | 84 | 고전적인 단조 스택 문제. 각 막대마다 그 막대가 가장 짧은 막대가 되는 가장 넓은 직사각형을 찾습니다. |
| 부분 배열 최소값의 합 | 907 | max(min * sum) 대신 모든 min‑product를 합합니다. 경계 찾이는 동일하지만 집계 방식이 다릅니다. |
| 부분 배열 범위의 합 | 2104 | 두 개의 스택(하나는 증가, 하나는 감소)을 사용해 각 요소의 최소 기여와 최대 기여를 모두 계산합니다. |
| 빗물 채우기 | 42 | 단조 감소 스택을 사용합니다. 팝할 때 경계가 물을 가둘 수 있는 너비와 높이를 제공합니다. |
| 다음 큰 요소 II | 503 | 더 간단한 버전. 접두합 레이어 없이 팝 메커니즘을 이해하기 위한 좋은 워밍업입니다. |
추천 순서:
- 84 – 방금 해결한 문제와 가장 가깝습니다.
- 907 – 동일한 아이디어를 다른 집계 방식으로 확장합니다.
- 나머지 문제들은 원하는 순서대로 풀어도 됩니다.
저는 이런 문제들을 더 잘 풀 수 있도록 돕기 위해 Levelop 를 만들고 있습니다. 이런 식의 추가 분석을 원한다면 확인해 보세요.