[LeetCode] 152. Maximum Product Subarray

class Solution {
    public int maxProduct(int[] nums) {
        int numsLength = nums.length;
        int max = nums[0];
        int min = nums[0];
        int result = nums[0];
        
        for(int idx = 1; idx < numsLength; idx++){
            max = Math.max(nums[idx], Math.max(max*nums[idx], min*nums[idx]));
            min = Math.min(nums[idx], Math.min(max*nums[idx], min*nums[idx]));
            result = Math.max(result, Math.max(max, min));
        }
        
        return result;
    }
}​

Maximum Product Subarray - LeetCode

직전 문제와 같은 것 같지만 다르다! 이번엔 곱셈이다

 

// 이전 문제 풀이

[LeetCode] 53. Maximum Subarray

문제 설명

Given an integer array nums, find a contiguous non-empty subarray within the array 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.

A subarray is a contiguous subsequence of the array.

 

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.

 

Constraints:

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

오답

: min 을 비교하면서 Set 할 때,  현재 index 기준이 아니라 max 값이 set 된 상태에서 min 값을 비교하고 result 값도 마찬가지로 현재 index 기준이 아니기 때문에 틀린 풀이 방법이다.

class Solution {
    public int maxProduct(int[] nums) {
        int numsLength = nums.length;
        int max = nums[0];
        int min = nums[0];
        int result = nums[0];
        
        for(int idx = 1; idx < numsLength; idx++){
            max = Math.max(nums[idx], Math.max(max*nums[idx], min*nums[idx]));
            min = Math.min(nums[idx], Math.min(max*nums[idx], min*nums[idx]));
            result = Math.max(result, Math.max(max, min));
        }
        
        return result;
    }
}

 

정답

: 현재 index 기준 값을 저장해둘 변수를 선언하여 오답의 원인을 해결함.

class Solution {
    public int maxProduct(int[] nums) {
        int numsLength = nums.length;
        int max = nums[0];
        int min = nums[0];
        int result = nums[0];
        
        for(int idx = 1; idx < numsLength; idx++){
            int now = nums[idx];
            int tmpMax = max * now;
            int tmpMin = min * now;
            
            max = Math.max(now, Math.max(tmpMax, tmpMin));
            min = Math.min(now, Math.min(tmpMax, tmpMin));
            
            result = Math.max(result, max);
        }
        
        return result;
    }
}