[leetcode] Maximum Product Subarray

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

Maximum Product Subarray - LeetCode

 

연속된 수를 곱한 결과 중 가장 큰 것을 찾아내는 문제입니다. 

음수 * 음수 = 양수인 케이스를 고려해야 합니다.

곱셈의 결과가 음수가 된 경우에는 min (최소값)으로 저장해둡니다. 여기에 다시 음수를 곱하게 되면, 곱셈의 결과를 max(최대값)으로 저장합니다. 이렇게 음수가 등장할때마다 곱셈의 결과인 min과 max를 바꾸어 가며 계산합니다. 

class Solution {
    public int maxProduct(int[] nums) {
        int maxProduct = Integer.MIN_VALUE;
        int max = 1;
        int min = 1;

        for (int num : nums) {

            if(num < 0){
                int temp = max;
                max = min;
                min = temp;
            }
            max = Math.max(num, max * num);
            min = Math.min(num, min * num);

            maxProduct = Math.max(max, maxProduct);
        }
        return maxProduct;
    }
}