LeetCode 1567. Maximum Length of Subarray with Positive Product 해설, 풀이, 파이썬
접근
- linear 로 훝으며 모든 값을 곱하며 진행한다. 메모리 절약을 위해 부호만 기록한다.
- 각 index 에서 여태의 곱연산 부호에 따라 조건부로 최대 부분 수열 길이를 갱신한다.
- 0 을 만나면 필요한 변수들 초기화한다.
사고
0은 처리해줘야 하고, 양수는 곱해져도 어딜 slicing 하는지에 따라 부호가 바뀌지 않는다. 따라서 0이 아닌 값들을 쭉 이어서 길이를 기억한다. 첫번재 음수가 나오는 인덱스를 표시해놓고 현재 pointer 까지 곱연산이 양수이면 현재 까지 이어진 값의 길이와 max 를 비교해서 값을 갱신하고 음수라면 (pointer - 첫번째 음수 인덱스) 와 max 를 비교하여 갱신한다.
class Solution:
def getMaxLen(self, nums: list[int]) -> int:
pos = 0 # 0 if product is negative, 1 otherwise
result = 0 # maximum length of subarray
length = 0 # current length of subarray
neg_index = -1 # index of the first negative value in current subarray
for i in range(len(nums)):
if nums[i] == 0:
length = 0
neg_index = -1
pos = 0
elif nums[i] > 0:
if length == 0:
pos = 1
length += 1
if pos:
result = max(result, length)
else:
result = max(result, i - neg_index)
else:
if neg_index < 0:
neg_index = i
if length > 0:
pos ^= 1
length += 1
if pos:
result = max(result, length)
else:
result = max(result, i - neg_index)
return result
