최대 부분 배열곱 문제
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.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
체크해야할 점
- 음수와 음수가 만나면 양의 정수가 된다.
풀이 방법
곱셈의 경우 음수가 없다면 문제가 매우 단순해진다.
global_max와 curr_max를 계속해서 갱신해가면서 한번의 루프를 돌면 된다.
파이썬 코드로 구현하면 아래와 같다.
curr_max = global_max = nums[0]
for i in nums[1:]:
# if i == 0 next curr_max will be changed.
curr_max = max(curr_max*i, i)
global_max = max(curr_max, global_max)
return global_max 하지만 음수가 들어간다면 엣지 케이스를 계속해서 고민해줘야 한다.
음수가 포함된다면 우리는 반드시 최소값을 계속해서 갱신해줘야 한다.
최소값이 음수일때 i 도 음수라면 최대값이 될 수도 있기 때문이다.
따라서 파이썬 코드로 구현하면 다음과 같다.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
## APPROACH : KADANES ALGORITHM ##
## TIME COMPLEXITY : O(N) ##
## SPACE COMPLEXITY : O(1) ##
# 1. Edge Case : Negative * Negative = Positive
# 2. So we need to keep track of minimum values also, as they can yield maximum values.
answer = prev_max = prev_min = nums[0]
for i in nums[1:]:
# if prev_min or prev_max == o case: i could min or max
curr_min = min(prev_min*i, prev_max*i, i)
curr_max = max(prev_min*i, prev_max*i, i)
answer = max(answer, curr_max)
# update prev value
prev_min = curr_min
prev_max = curr_max
return answer