문제 설명

정수 배열 nums가 주어졌을 때, 곱이 양수인 가장 긴 부분 배열의 길이를 찾아보세요.

부분 배열은 원래 배열에서 연속된 0개 이상의 숫자로 이루어진 배열입니다.

예시 1:

입력: nums = [1,-2,-3,4]
출력: 4
설명: 배열 자체의 곱이 양수 24입니다.

예시 2:

입력: nums = [0,1,-2,-3,-4]
출력: 3
설명: 곱이 양수인 가장 긴 부분 배열은 [1,-2,-3]이며, 곱은 6입니다.
0을 포함할 수 없음에 유의하세요. 그렇게 하면 곱이 0이 되어 양수가 아니기 때문입니다.

예시 3:

입력: nums = [-1,-2,-3,0,1]
출력: 2
설명: 곱이 양수인 가장 긴 부분 배열은 [-1,-2] 또는 [-2,-3]입니다.

해결 방법

동적 프로그래밍 접근법

이 문제를 해결하기 위해 동적 프로그래밍을 사용하겠습니다. 다음과 같은 단계로 접근할 수 있습니다:

1. 상태 정의
2. 상태 전이 방정식
3. 초기화
4. 채우는 순서
5. 반환 값

상태 정의

• positive[i]: i번째 요소로 끝나는 모든 부분 배열 중 곱이 양수인 가장 긴 부분 배열의 길이
• negative[i]: i번째 요소로 끝나는 모든 부분 배열 중 곱이 음수인 가장 긴 부분 배열의 길이

상태 전이 방정식

각 위치를 순회하면서 두 동적 프로그래밍 배열의 값을 동시에 업데이트합니다.

positive[i]에 대해 nums[i]의 값에 따라 세 가지 경우로 나눌 수 있습니다:

1. nums[i] = 0일 때: i로 끝나는 모든 부분 배열의 곱은 양수가 될 수 없으므로 positive[i] = 0
2. nums[i] > 0일 때: positive[i] = positive[i-1] + 1 (만약 positive[i-1]이 0이면 1이 됨)
3. nums[i] < 0일 때:
   • 만약 negative[i-1] = 0이면, i-1로 끝나는 음수 곱 부분 배열이 없으므로 positive[i] = 0
   • 만약 negative[i-1] != 0이면, 음수 × 음수 = 양수이므로 positive[i] = negative[i-1] + 1

마찬가지로, negative[i]에 대해:

1. nums[i] = 0일 때: negative[i] = 0
2. nums[i] > 0일 때: negative[i] = negative[i-1] == 0 ? 0 : negative[i-1] + 1
3. nums[i] < 0일 때: negative[i] = positive[i-1] + 1

초기화

배열의 앞에 하나의 칸을 추가하고 positive[0] = negative[0] = 0으로 설정합니다.

채우는 순서

상태 전이 방정식에 따라, 채우는 순서는 '왼쪽에서 오른쪽으로, 두 배열을 함께 채우는' 방식입니다.

반환 값

positive 배열의 최대값을 반환합니다.

코드 구현

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        
        // i번째 요소로 끝나는 부분 배열 중 곱이 양수/음수인 가장 긴 길이
        vector<int> positive(n + 1, 0);
        vector<int> negative(n + 1, 0);
        
        int max_length = 0;
        
        for (int i = 1; i <= n; i++) {
            if (nums[i-1] > 0) {
                // 현재 수가 양수이면
                positive[i] = positive[i-1] + 1;
                negative[i] = (negative[i-1] == 0) ? 0 : negative[i-1] + 1;
            } else if (nums[i-1] < 0) {
                // 현재 수가 음수이면
                positive[i] = (negative[i-1] == 0) ? 0 : negative[i-1] + 1;
                negative[i] = positive[i-1] + 1;
            } else {
                // 현재 수가 0이면
                positive[i] = 0;
                negative[i] = 0;
            }
            
            // 최대 길이 업데이트
            max_length = max(max_length, positive[i]);
        }
        
        return max_length;
    }
};