[Leetcode] 152. Maximum Product Subarray
4279 ワード
問題のショートカット
Time Complexity: O(n)O(n)O(n)
Space Complexity: O(1)O(1)O(1)
Time Complexity: O(n)O(n)O(n)
Space Complexity: O(1)O(1)O(1)
class Solution:
def maxProduct(self, nums: List[int]) -> int:
"""
0이 아닌 정수가 주어졌을 때, 연속되는 곱의 최대값은 모든 수의 곱과 처음 등장하는 음수 다음
수부터 곱한 수 중 양수인 수를 고르면 된다.
음수의 수가 홀수이면 첫 음수 이후부터의 누적 곱, 짝수이면 모든수의 곱이 정답이 된다.
0이 존재한다면 0 이전까지의 최대 값과 0 이후의 최대 값을 비교하면 된다. 0을 곱하면 0이므로
연속된 곱이 의미가 없기 때문이다.
"""
maxSoFar = float("-inf")
posProdSoFar = negProdSoFar = None
for num in nums:
if num == 0:
maxSoFar = max(maxSoFar, posProdSoFar or num)
posProdSoFar = negProdSoFar = None
elif num < 0:
maxSoFar = max(maxSoFar, posProdSoFar or num)
posProdSoFar, negProdSoFar = negProdSoFar, posProdSoFar
negProdSoFar = negProdSoFar * num if negProdSoFar else num
if posProdSoFar: posProdSoFar *= num
else:
posProdSoFar = posProdSoFar * num if posProdSoFar else num
if negProdSoFar: negProdSoFar *= num
if posProdSoFar:
maxSoFar = max(maxSoFar, posProdSoFar)
return maxSoFar
Reference
この問題について([Leetcode] 152. Maximum Product Subarray), 我々は、より多くの情報をここで見つけました https://velog.io/@haebin/Leetcode-152.-Maximum-Product-Subarrayテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol