Maximum Product Subarray
[문제]
Given an integer array nums, find a
subarray
that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
[입력 조건]
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
[내 풀이]
class Solution:
def maxProduct(self, nums: List[int]) -> int:
# subarray - 연속적으로
# find all product and sort isn't preferred
# 0를 기준으로 하는 것은 의미가 없다
# window를 하나 두고 넣고 빼고? dp
if not nums:
return 0
# 현재 인덱스에서 끝나는 최대 및 최소 곱 추적
max_product = min_product = result = nums[0]
# 배열 nums를 반복
for i in range(1, len(nums)):
# 현재 값이 음수일 경우 최대 및 최소 곱을 교환
if nums[i] < 0:
max_product, min_product = min_product, max_product
# 최대 및 최소 곱 갱신
max_product = max(nums[i], nums[i] * max_product)
min_product = min(nums[i], nums[i] * min_product)
# 최대 곱 업데이트
result = max(result, max_product)
return result
이 문제를 해결하기 위해 사용한 알고리즘은 동적 프로그래밍(Dynamic Programming)입니다. 이 알고리즘은 입력 배열을 한 번만 반복하면서 현재 인덱스까지의 최대 및 최소 곱을 갱신하고, 그 중 최대값을 추적하여 부분 배열의 최대 곱을 찾습니다.
주어진 배열에서 음수가 나오면 최대 및 최소 곱을 교환하는 방식으로, 음수가 연속적으로 등장하는 경우에도 올바른 최대 곱을 찾을 수 있습니다. 이 방식은 입력 배열을 한 번만 스캔하므로 선형 시간 복잡도인 O(n)에 문제를 효율적으로 해결할 수 있습니다.
분할 정복과 dp의 공톰점과 차이점도 공부하였는데,
공통점은 분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점입니다.
차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 것입니다.
[출처]
https://leetcode.com/problems/maximum-product-subarray/description/
