[PS] Leet | 152. 최댓값을 가지는 하위 배열 - 곱셈

문제

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.

예시

Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

조건

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

답

배열 안에 음수도 섞여 있기 때문에, 부호가 바뀌는 것을 고려하여 절댓값이 최소인 경우도 함께 고려해야 합니다.

 

절댓값이 최대인 경우(maxProduct)와 최소인 경우(minProduct)를 함께 갱신하면서, 음수인 숫자가 나오면 두 수를 뒤바꿉니다.

 

첫 요소가 양수인 경우 maxProduct가, 음수인 경우 minProduct가 최댓값을 추적합니다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let maxProduct = nums[0];
    let minProduct = nums[0];
    let totalMaxProduct = nums[0];

    for (let i=1; i<nums.length; ++i) {
        if (nums[i] < 0) {
            [maxProduct, minProduct] = [minProduct, maxProduct];
        }

        if (nums[i] === 0) {
            [maxProduct, minProduct] = [0, 0];
        }

        maxProduct = Math.max(nums[i], maxProduct * nums[i]);
        minProduct = Math.min(nums[i], minProduct * nums[i]);

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

    return totalMaxProduct;
};