LeetCode : Maximum Product Subarray (Medium)
4534 단어 coding testcoding test
0. Overview
- 풀이 날짜 :
2021-06-18
- 풀이 소요 시간 :
30m
- LeetCode URL : https://leetcode.com/problems/maximum-product-subarray/
1. Problem
2. Solution
from typing import List
def maxProduct(nums: List[int]) -> int:
min_candidates = [n for n in nums]
max_candidates = [n for n in nums]
for i in range(1, len(nums)) :
max_candidates[i] = max(min_candidates[i-1] * nums[i], max_candidates[i-1] * nums[i], max_candidates[i])
min_candidates[i] = min(min_candidates[i-1] * nums[i], max_candidates[i-1] * nums[i], min_candidates[i])
#print(max_candidates, min_candidates)
return max(max_candidates)
3. Review
- 앞서 풀이한 'Maximum Subarray' 문제와 동일하게 Dynamic Programming 방식을 활용하여 문제를 해결할 수 있습니다.
- 누적합을 구하는 문제와 달리, 음수 여부에 따라 누적 곱이 달라질 수 있으므로,
i
번째Subarray
까지 최대/최소 누적 곱을 유지하는 리스트를 생성하여, 비교를 통해 최대 누적곱 값을 구할 수 있습니다.
Author And Source
이 문제에 관하여(LeetCode : Maximum Product Subarray (Medium)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@star7357/LeetCode-Maximum-Product-Subarray-Medium저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)