[LeetCode] 152. Maximum Product Subarray - Java

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

Maximum Product Subarray - LeetCode

---

문제

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.

 

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.

---

풀이

풀이 과정

정수 배열 nums 가 주어질 때 부분 배열의 곱이 가장 큰 값을 return하는 문제이다.

dp를 이용하여 각 인덱스마다 부분배열의 최대 곱셈 값을 저장한다. 곱셈의 경우 음수끼리 곱하게 되면 양수가 되어 최대값이 될 가능성이 있기 때문에 부분배열의 최소 곱셈 값 역시 저장한다.

각 인덱스별 최대 곱셈 값과, 최소 곱셈 값을 저장할 정수 배열과 정답을 저장할 정수 변수를 선언하고 배열의 첫번째 값은 num배열의 첫 번째 인덱스 값으로 초기화한다.

int[] minArr = new int[nums.length]; // 부분배열의 곱 최소값 배열
int[] maxArr = new int[nums.length]; // 부분배열의 곱 최대값 배열
int maxProd; // 부분배열의 곱 최대값

minArr[0] = maxArr[0] = maxProd = nums[0]; // 첫 번째 인덱스 값으로 각각 초기화

 

num배열을 차례대로 탐색하며 최소값과 최대값을 각각 구한다.
i번째 인덱스에서 탐색할 수 있는 결과값의 경우의 수는 세 가지로 볼 수 있다.

1. 현재 인덱스값
2. 이전 인덱스 최소값 x 현재 인덱스 값
3. 이전 인덱스 최대값 x 현재 인덱스 값

위의 세가지 경우 중 최소값과 최대값을 각각 구하여 저장하고 현재 인덱스의 결과값이 최대값이 된다면 최대값을 갱신한다.

for(int i = 1; i < nums.length; i++) {
    /*
     * i번째 인덱스에서 부분배열의 곱 최소값
     * 
     * 1. 현재 인덱스값
     * 2. 이전 인덱스 최소값 * 현재 인덱스 값
     * 3. 이전 인덱스 최대값 * 현재 인덱스 값
     * 
     * 3가지 중 최소값
     * 
     */
    minArr[i] = Math.min(nums[i], Math.min(minArr[i - 1] * nums[i], maxArr[i - 1] * nums[i]));

    /*
     * i번째 인덱스에서 부분배열의 곱 최대값
     * 
     * 1. 현재 인덱스값
     * 2. 이전 인덱스 최소값 * 현재 인덱스 값
     * 3. 이전 인덱스 최대값 * 현재 인덱스 값
     * 
     * 3가지 중 최대값
     * 
     */
    maxArr[i] = Math.max(nums[i], Math.max(minArr[i - 1] * nums[i], maxArr[i - 1] * nums[i]));

    maxProd = Math.max(maxProd, maxArr[i]); // 부분배열의 곱 최대값 갱신
}

 

탐색이 끝나면 부분배열의 곱 최대값을 return한다.

return maxProd;

---

최종 코드

class Solution {
    public int maxProduct(int[] nums) {
        int[] minArr = new int[nums.length]; // 부분배열의 곱 최소값 배열
        int[] maxArr = new int[nums.length]; // 부분배열의 곱 최대값 배열
        int maxProd; // 부분배열의 곱 최대값
        
        minArr[0] = maxArr[0] = maxProd = nums[0]; // 첫 번째 인덱스 값으로 각각 초기화
        
        for(int i = 1; i < nums.length; i++) {
            /*
             * i번째 인덱스에서 부분배열의 곱 최소값
             * 
             * 1. 현재 인덱스값
             * 2. 이전 인덱스 최소값 * 현재 인덱스 값
             * 3. 이전 인덱스 최대값 * 현재 인덱스 값
             * 
             * 3가지 중 최소값
             * 
             */
            minArr[i] = Math.min(nums[i], Math.min(minArr[i - 1] * nums[i], maxArr[i - 1] * nums[i]));
            
            /*
             * i번째 인덱스에서 부분배열의 곱 최대값
             * 
             * 1. 현재 인덱스값
             * 2. 이전 인덱스 최소값 * 현재 인덱스 값
             * 3. 이전 인덱스 최대값 * 현재 인덱스 값
             * 
             * 3가지 중 최대값
             * 
             */
            maxArr[i] = Math.max(nums[i], Math.max(minArr[i - 1] * nums[i], maxArr[i - 1] * nums[i]));
            
            maxProd = Math.max(maxProd, maxArr[i]); // 부분배열의 곱 최대값 갱신
        }

        return maxProd;
    }
}

---