728x90
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)
기존에 냈던 답
728x90
'Python' 카테고리의 다른 글
167. Two Sum II - Input Array Is Sorted - 번외 알고리즘 코딩 인터뷰 (0) | 2022.09.01 |
---|---|
33. Search in Rotated Sorted Array - 1주차 알고리즘 코딩 인터뷰 공부 (0) | 2022.08.31 |
1주차 파이썬 알고리즘- 217. Contains Duplicate (0) | 2022.07.29 |
1주차 - 121. Best Time to Buy and Sell stock [코딩 인터뷰 공부] (0) | 2022.07.25 |
1주차 - 53. Maximum Subarray [코딩 인터뷰 공부] (0) | 2022.07.08 |