Maximum Product Subarray

+10

nums의 부분 배열 원소들을 모두 곱한 뒤, 부분 배열이 만들 수 있는 가장 큰 곱을 반환하세요. 부분 배열은 간격 없이 연속된 원소를 포함하며 비어 있지 않으므로, 음수로만 이루어진 배열도 답이 있습니다. 0과 음수 값도 허용됩니다.

함수

maxProduct(nums: integer-array) → integer

numsinteger-array: -10에서 10 사이의 정수들을 곱합니다
반환값integer: 비어 있지 않은 부분 배열의 최댓값

제약 조건

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
모든 부분 배열의 곱은 32비트 부호 있는 정수 범위에 들어갑니다.

예제

입력: nums = [2, -5, 3, -2, 0, 4]
출력: 60
설명: 음수 두 개는 서로 상쇄됩니다: 2 × -5 × 3 × -2 = 60. 0이 배열을 둘로 나누며, 반대편의 4는 60을 이길 수 없습니다.

입력: nums = [-2, 3, -4, -1]
출력: 24
설명: 배열 전체의 곱은 음수가 세 개 있으므로 -24입니다. 마지막 요소를 제외하면 음수가 두 개 남습니다. -2 × 3 × -4 = 24이며, 이는 첫 번째 요소를 제외했을 때 얻는 12보다 큽니다.

입력: nums = [-6, 0, -7]
출력: 0
설명: 0을 포함하지 않는 부분 배열은 음수 하나이고, 0을 포함하는 부분 배열의 곱은 0입니다. 가장 좋은 선택은 부분 배열 [0]입니다.

후속 질문

최적의 부분 배열이 시작하고 끝나는 위치도 O(n) 시간과 O(1) 공간으로 어떻게 알아낼 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

음수를 곱하면 곱의 순서가 뒤바뀌므로, 지금까지 가장 작은 곱이 다음 단계에서 가장 큰 곱이 될 수 있고, 0을 곱하면 모든 곱이 0이 됩니다. 각 인덱스에서 값 하나가 아니라 그 위치에서 끝나는 부분 배열의 최댓값과 최솟값, 두 값을 유지하면 한 번만 순회해도 충분합니다.

각 시작점에서 모든 부분 배열을 곱하세요

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

핵심 아이디어

시작 인덱스를 고정하고 끝 인덱스를 오른쪽으로 이동하면서, 새 요소마다 누적 product를 곱합니다. 각 단계 후 최댓값과 비교하면 모든 부분 배열을 한 번씩 확인하게 됩니다. 답이 음수일 수도 있으므로 best를 nums[0]으로 시작합니다.

시작 인덱스와 끝 인덱스의 쌍은 약 n²/2개이고, 각 쌍마다 곱셈을 한 번씩 합니다. 요소가 20,000개라면 2 × 10^8번입니다.

알고리즘

best를 nums[0]으로 설정합니다.
각 start에 대해 product를 1로 설정합니다.
end를 start부터 마지막 인덱스까지 이동시키며 product에 nums[end]를 곱합니다.
product가 best보다 크면 해당 값을 저장합니다.
best를 반환합니다.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

양쪽 끝에서 스캔하고, 0에서 다시 시작하기

핵심 아이디어

0은 배열을 0이 없는 구간들로 나눕니다. 한 구간 안의 모든 값은 절댓값이 1 이상이므로, 더 긴 부분 배열의 절댓값 곱이 더 작아지는 일은 없습니다. 달라지는 것은 부호뿐입니다. 음수가 짝수 개 있으면 구간 전체가 최선입니다. 음수가 홀수 개 있으면 음수 하나를 제외해야 하며, 첫 번째 음수와 그 앞의 모든 원소를 제외하거나 마지막 음수와 그 뒤의 모든 원소를 제외하는 것이 최선입니다. 어느 쪽이든 구간의 접미사 또는 접두사를 남기게 됩니다.

왼쪽에서 오른쪽으로 한 번 순회하면서 누적 곱으로 모든 접두사를 확인하고, 0을 만나면 누적 곱을 1로 재설정합니다. 오른쪽에서 왼쪽으로 한 번 순회하면서 모든 접미사를 확인합니다. [-2, 3, -4, -1]에서 왼쪽 순회는 -2, -6, 24, -24를 확인하고, 오른쪽 순회는 -1, 4, 12, -24를 확인하므로 답은 24입니다. 이 논리는 0이 아닌 모든 값의 절댓값이 1 이상이어야 하며, 이는 정수에서 성립합니다.

알고리즘

best를 nums[0]으로 설정하고 product를 1로 설정합니다.
왼쪽에서 오른쪽으로 순회하며 각 요소를 product에 곱하고, best와 product 중 더 큰 값을 유지합니다.
product가 0이 될 때마다 다음 실행을 새로 시작할 수 있도록 다시 1로 설정합니다.
product를 다시 1로 설정하고 오른쪽에서 왼쪽으로 같은 방식으로 순회합니다.
best를 반환합니다.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

여기서 끝나는 곱 중 가장 큰 값과 가장 작은 값 추적하기

핵심 아이디어

인덱스 i에서 끝나는 모든 부분 배열은 nums[i]만으로 이루어지거나, nums[i]에 i-1에서 끝나는 부분 배열을 곱한 것입니다. nums[i]가 음수이면, 이 곱들 중 가장 큰 값은 i-1에서 끝나는 가장 작은 곱에서 나옵니다. 따라서 현재 인덱스에서 끝나는 부분 배열의 곱 중 가장 큰 값과 가장 작은 값인 high와 low를 모두 유지합니다. 새로운 high는 num, high × num, low × num 중 가장 큰 값이고, 새로운 low는 가장 작은 값입니다. num만 사용하는 것은 0 이후에 연속 구간을 다시 시작하는 역할을 합니다.

첫 번째 예시에서 -2가 나왔을 때 low는 -30이고, -30 × -2 = 60이 high가 되어 정답이 됩니다.

알고리즘

high, low 및 best를 nums[0]으로 설정합니다.
이후 각 요소 num에 대해 a = high × num 및 b = low × num을 계산합니다.
num, a, b 중 가장 큰 값으로 high를 설정하고, 가장 작은 값으로 low를 설정합니다.
best와 high 중 더 큰 값으로 best를 설정합니다.
best를 반환합니다.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

함정과 경계 사례

가장 큰 곱만 추적합니다. 첫 번째 예시에서는 -2가 -30을 60으로 바꾸는 것을 놓치기 때문에 60 대신 4를 반환합니다.
이미 업데이트된 high에서 새 low를 계산합니다. 둘 중 하나를 변경하기 전에 high × num과 low × num을 저장하세요.
best를 0이나 1로 시작합니다. 부분 배열은 비어 있을 수 없으므로 [-3]은 -3을 반환해야 합니다.
두 번 통과하는 방법에서 왼쪽 방향 통과만 실행합니다. [-2, 3, 4]에서는 -2보다 큰 값을 보지 못하지만, 접미 배열 [3, 4]의 곱은 12입니다.
JavaScript, TypeScript, Lua에서는 음수에 0을 곱하면 -0이 되어 마이너스 기호와 함께 출력됩니다. 반환하기 전에 결과에 0을 더하세요.

자주 묻는 질문3

최대 곱 부분 배열의 시간 복잡도는 얼마인가요?

각 인덱스에서 끝나는 가장 큰 곱과 가장 작은 곱을 추적하면 O(n) 시간과 O(1) 공간이 필요합니다. 두 번 순회하는 접두사 및 접미사 방법도 비용은 같습니다. 각 시작점에서 모든 부분 배열을 곱하면 O(n²) 시간이 필요합니다.

Maximum Product Subarray에서 최솟값이 필요한 이유는 무엇인가요?

음수는 이전 인덱스에서 끝나는 가장 작은 곱을 가장 큰 곱으로 바꿉니다. 가장 큰 곱만 유지하면 필요할 때 그 후보는 사라집니다. [3, -2, -4]에서 -4 이전의 가장 작은 곱은 -6이고, -6 × -4 = 24가 정답입니다.

최대 곱 부분 배열은 최대 부분 배열과 어떻게 다른가요?

합에서는 음수인 누적 합은 언제나 불리하므로 인덱스마다 값 하나면 충분합니다. 곱에서는 음수인 누적 값이 음수가 하나 더 나온 뒤 최댓값이 될 수 있고, 0은 모든 것을 초기화합니다. 따라서 곱 버전에서는 각 인덱스에서 가장 큰 곱과 가장 작은 곱을 유지합니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

nums = [2, -5, 3, -2, 0, 4]

예상 출력

Maximum Product Subarray

함수

제약 조건

예제

힌트

풀이

각 시작점에서 모든 부분 배열을 곱하세요

양쪽 끝에서 스캔하고, 0에서 다시 시작하기

여기서 끝나는 곱 중 가장 큰 값과 가장 작은 값 추적하기

함정과 경계 사례

자주 묻는 질문3

비슷한 문제