[Leet Code] Maximum Product Subarray (Java)

문제는 아래와 같다.

Given an integer array nums, find a
subarray
that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer

Leet Code Maximum Product Subarray 문제

Leet Code Maximum Subarray와 비슷한 문제였다. 이 문제는 subarray 요소(element)들을 곱한 값의 최댓값을 구하는 것이고, Maximum Subarray는 요소들을 더한 값의 최댓값을 구하는 문제다.

Leet Code Maximum Subarray 문제(유사한 문제)

Leet Code Maximum Subarray 문제 풀이

Maximum Subarray와 같은 방법으로 풀면 음수가 짝수 번 곱해져 생기는 최댓값을 처리하지 못한다. 입력값의 형태가 int이고, 음수가 짝수 번 곱해져 생기는 최댓값은 음수인 최솟값와 음수인 요소가 곱해져 만들어진다는 것에 집중해야 한다.

즉, 각 요소에서의 최댓값과 최솟값을 모두 업데이트하여 음수가 짝수 번 곱해지는 최댓값도 알 수 있다.

class Solution {
    public int maxProduct(int[] nums) {
        int maxCurV = nums[0];
        int minCurV = nums[0];
        int maxV = nums[0];
        int minV = nums[0];
        for(int i = 1; i < nums.length; i++)    # 최소값과 최댓값을 모두 구하여 음수도 포함
        {
            int maxTmp = maxCurV;
            int minTmp = minCurV;
            maxCurV = Math.max(nums[i], minCurV * nums[i]);
            maxCurV = Math.max(maxCurV, maxTmp * nums[i]);
            maxV = Math.max(maxCurV, maxV);
            minCurV = Math.min(nums[i], maxTmp * nums[i]);
            minCurV = Math.min(minCurV, minTmp * nums[i]);
            minV = Math.min(minCurV, minV);
            System.out.printf("%d   %d\n", maxV, minV);
        }
        return maxV;
    }
}```