[Python] 1567. Maximum Length of Subarray With Positive Product (Medium)

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

Maximum Length of Subarray With Positive Product - LeetCode

 

곱이 양의 정수가 되는 가장 긴 부분수열의 길이를 구하는 문제입니다.

고려해야할 조건은 다음과 같습니다.

 

1. 중간에 0이 들어가는 경우 어떻게 곱해도 0이 되기 때문에 양의 정수라는 조건을 충족시키지 못합니다. 그래서 부분수열은 0을 기준으로 끊어진 형태가 됩니다.

 

2. 부분수열 안에 음수가 짝수개 있으면 곱하면서 서로 상쇄되어 곱셈의 결과가 양의 정수가 됩니다.

 

3. 그럼 음수가 홀수개 있다면 어떨까요? 하나만 빼주면 짝수가 됩니다.

(음수가 1개 있어서 하나를 빼도 0개로 조건을 충족합니다.)

내 위치에서 가장 먼 음수를 빼고 그 다음부터 카운트 하는게 수열의 길이를 길게 만들겁니다.

그리고 내 위치에서 가장 먼 음수는 0 이후에 처음 나온 음수가 될겁니다.

 

코드로 구현하면 이렇습니다.

class Solution:
    def getMaxLen(self, nums: list) -> int:
        answer = -1
        zeroInedx = -1
        firstNegative = -1
        negativeCount = 0
        
        for i in range(0, len(nums)):
            if(nums[i] == 0):
                firstNegative = -1
                negativeCount = 0
                zeroInedx = i
            
            if(nums[i] < 0):
                negativeCount += 1 
                if(firstNegative == -1):
                    firstNegative = i
            
            if(negativeCount % 2 == 0):
                answer = max(answer, i - zeroInedx)
            else :
                answer = max(answer, i - firstNegative)
        
        return answer
    

input = [[1,-2,-3,4],[0,1,-2,-3,-4],[-1,-2,-3,0,1]]

for i in input:
    print(Solution().getMaxLen(i))