[LeetCode] 152. Maximum Product Subarray

문제

배열 문제이다.

53번은 합을 구하는 문제이고, 이 문제는 곱을 구하는 문제이다. (53번 설명 참조)

https://leetcode.com/problems/maximum-product-subarray/

Maximum Product Subarray - LeetCode

 

풀이

이 문제는 생각하기 조금 어려웠던 것 같다. 53문제 풀이를 참고하여 해결하려고 했는데, 조금 다른 문제였다.

 

비슷하게 product 변수에 첫 번째 원소부터 하나씩 곱해나간다.

 

처음으로 음수를 만나게 되면, 그 수까지 곱한 product를 따로 저장해놓는다.

(그다음수를 곱한 결과가 음수라면 값이 점점 작아지기 때문에 product에서 위에 따로 저장한 값을 나누어 준다.)

 

만약 0을 만나게 되면 product를 다시 1로 초기화하고, 계속 진행한다.

최댓값이 0보다 작다면 0으로 저장해 준다.

처음으로 음수를 만나 저장하는 것도 다시 진행한다.

(부분 배열 사이에 0이 있는 경우를 셀 필요 없음. 어차피 곱이 0이기 때문에)

 

코드

public int maxProduct(int[] nums) {
        int max = nums[0];
        int product = 1, firstNegative = 1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                firstNegative = 1;
                product = 1;
                if (max < 0)
                    max = 0;
            } else {
                product *= nums[i];
                if (product < 0)
                    max = Math.max(product / firstNegative, max);
                else
                    max = Math.max(product, max);
                if (firstNegative == 1 && nums[i] < 0)
                    firstNegative = product;
            }
        }

        return max;
    }