배열 nums가 주어졌을 때, 최소 한 개 이상의 숫자를 포함하는 연속된(contiguous) 부분 배열 중에서 요소들의 곱이 가장 큰 값을 찾는 문제입니다.
예를 들어 배열이 [1,9,2,0,2,5]라면, 연속 부분 배열 [1,9,2]의 곱인 18이 최댓값이므로 출력 결과는 18이 됩니다.
접근 방식: 동적 계획법(DP)
이 문제는 단순히 '현재까지의 최대 곱'만 추적하면 해결되지 않습니다. 배열에 음수가 포함되어 있으면, 지금까지의 최솟값(음수)에 음수가 다시 곱해져 오히려 가장 큰 양수가 될 수 있기 때문입니다.
따라서 각 위치마다 다음 두 가지 값을 함께 추적합니다:
- max_list[i]: i번째 요소까지 고려했을 때 만들 수 있는 최대 곱
- min_list[i]: i번째 요소까지 고려했을 때 만들 수 있는 최소 곱(음수 대비용)
구체적인 알고리즘은 다음과 같습니다.
- 길이가 len(nums)인 리스트
max_list와min_list를 준비합니다. - 두 리스트의 첫 번째 값은 모두
nums[0]으로 초기화합니다. - i를 1부터 배열 길이까지 반복하면서:
max_list[i]= max(max_list[i-1] * nums[i], min_list[i-1] * nums[i], nums[i])min_list[i]= min(min_list[i-1] * nums[i], nums[i], max_list[i-1] * nums[i])
- 반복이 끝나면
max_list의 최댓값을 반환합니다.
여기서 세 번째 후보인 nums[i] 자체를 비교에 포함하는 이유는, 앞선 곱들이 오히려 손해가 되는 경우(예: 앞의 값이 0이거나 작은 음수일 때) 새로운 부분 배열을 현재 위치에서 시작하는 것이 더 유리할 수 있기 때문입니다.
구현 예제
다음 코드로 실제 구현 과정을 확인해 보겠습니다.
class Solution(object):
def maxProduct(self, nums):
max_list = [0] * len(nums)
min_list = [0] * len(nums)
max_list[0] = nums[0]
min_list[0] = nums[0]
for i in range(1,len(nums)):
max_list[i] = max(max(max_list[i-1]*nums[i],min_list[i-1]*nums[i]),nums[i])
min_list[i] = min(min(min_list[i-1]*nums[i],nums[i]),max_list[i-1]*nums[i])
return max(max_list)
ob1 = Solution()
print(ob1.maxProduct([1,9,2,0,2,5]))입력
[1,9,2,0,2,5]
출력
18
동작 원리 살펴보기
위 예제에서 배열은 [1,9,2,0,2,5]입니다. 인덱스 0부터 차례로 진행하면 [1,9,2] 구간에서 곱이 18에 도달하고, 그다음 요소인 0이 등장하면 누적 곱이 초기화됩니다. 이후 [2,5] 구간의 곱은 10에 불과하므로, 전체 최댓값은 18이 유지됩니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 두 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 음수와 0이 섞여 있는 배열에서도 안정적으로 최대 곱을 찾을 수 있다는 점이 핵심 포인트입니다.