21-12-03
solved, but too iterative
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Max Subarray에서 사용한 Kadane's Algorithm과 비슷한 문제이다. 하지만 음수의 개수에 따라 Max product이 바뀔 수 있다는 점이 까다롭다.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
l=len(nums)
ans=max(nums)
dp=nums.copy()
if nums[0]<0:
lm=0
else:
lm=-1
for i in range(1,l):
v=nums[i]
if v<0 and lm==-1:
lm=i
if dp[i-1]==0:
continue
if v==0:
if lm!=-1 and lm!=i-1:
ans=max(ans,dp[i-1]//dp[lm])
lm=-1
continue
dp[i]=dp[i-1]*v
ans=max(ans,dp[i])
if lm!=-1 and lm!=l-1:
ans=max(ans,dp[l-1]//dp[lm])
print(dp,lm)
return ans
dp[i]는 i번째 원소로 마지막으로하는 subarray의 누적 product이다. 여기서 lm이 등장하는데 subarray에서 leftmost 음의 element index이다. lm을 구하는 이유는, subarray에서 가장 왼쪽 음수를 포함한 왼쪽 subarray를 제외한 나머지 subarray의 product을 구하기 위함이다.
이 풀이의 단점은 corner case에 취약하다는 점이다. [-1,-2,-3,0] 등 음수가 반복적으로 나오는 상황을 따로 처리해줘야한다.
if not nums:
return 0
if len(nums) == 1:
return nums[0]
min_so_far, max_so_far, max_global = nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
max_so_far, min_so_far = max(min_so_far*nums[i], max_so_far*nums[i], nums[i]), min(min_so_far*nums[i], max_so_far*nums[i], nums[i])
max_global = max(max_global, max_so_far)
return max_global
아이디어가 명확하고 코드가 직관적이다.
다음과 같은 Kadane's Algorithm의 핵심 아이디어가 들어가있다.
global maximum is the larger one between a local maximum and the previous global maximum.
이 문제에서는 특히 min_so_far이 음수를 만나 max_so_far로 업데이트 된다는 특징을 잘 캐치해야한다. 따라서 max_so_far뿐만 아니라 min_so_far도 dp로 tracking한다.
def maxProduct(self, A):
B = A[::-1]
for i in range(1, len(A)):
A[i] *= A[i - 1] or 1
B[i] *= B[i - 1] or 1
return max(A + B)
보다 직관적인 풀이 방법이다. 사실 lm를 두지 않더라도, 오른쪽에서부터 누적 product을 구하고 max 값을 구하면 된다는 아이디어를 가지고 있다. A[i-1]이 0이 되는 경우는 이전 숫자가 1인 것으로 처리해서, A[i]에 그 value만 남기게 해주었다.