1주차 파이썬 알고리즘- 152. Maximum Product Subarray

152. Maximum Product subarray

정수로 이루어진 nums array 에서 연속된 정수로 이루어진 subarray 중, 정수의 곱이 최대인 값을 구하시오.

 

Given an integer array nums, find a contiguous non-empty subarray within the array 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.

A subarray is a contiguous subsequence of the array.

 

예시 1

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] nums의 subarray 중 2 곱하기 3의 값인 6이 최대.

예시 2

Input: nums = [-2,0,-1]
Output: 0
Explanation: 최대값은 -2와 -1 가 연속된 subarray 가 아니기 때문에 2가 될 수 없다.

.

.

.

.

.

.

문제 풀이

max_product = nums[0]
product = 1

for l in range(0, len(nums), 1):
    product = product * nums[l]
    max_product = max(product, max_product)
    if product == 0:
        product = 1

product = 1

for r in range(len(nums)-1, 0, -1):
    product = product * nums[r]
    max_product = max(product, max_product)
    if product == 0:
        product = 1

return max_product

런타임: 99ms, 42.24%

메모리 사용: 14.1MB, 20.35%

 

시간 복잡도: O(n)

공간 복잡도: O(1)

 

 

기존에 냈던 답