[leetcode #152] Maximum Product Subarray

Problem

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed 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 * 10⁴
・ -10 <= nums[i] <= 10
・ The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Idea

전체 수를 모두 곱한 값이 최대가 되는 subarray를 찾아 최대값을 리턴하면 되는 문제다.

실제 subarray를 리턴할 필요는 없으므로 주어진 인자인 array를 돌면서 최대값을 계산하기만 하면 된다.

처음에는 값이 양수인지 음수인지 구분하고 조건이 이것저것 들어간 상태로 풀었다. 하지만 다른 사람의 풀이를 보니 그럴 필요가 전혀 없다는 사실을 알게 되었다.

우선 각 index 별로 최대값과 최소값을 저장하는 dp array를 만든다. 최대값과 최소값, 리턴할 결과값을 각각 첫 원소값으로 설정한다.

array를 돌면서 원소가 양수인지, 음수인지에 따라 최대값과 최소값을 다르게 설정한다. 양수일 경우 최대값에 원소값을 곱한 값이 최대가 되며, 음수일 경우 최소값에 원소값을 곱한 값이 최소가 되는 것이다. 매번 리턴할 값과 최대값을 비교하여, 최대값이 더 크다면 리턴할 값을 최대값으로 만들어준다.

탐색이 끝난 뒤 값을 리턴하기만 하면 된다.

Solution

class Solution {
    public int maxProduct(int[] nums) {
        int[] max = new int[nums.length];
        int[] min = new int[nums.length];

        max[0] = min[0] = nums[0];
        int result = nums[0];

        for(int i=1; i<nums.length; i++){
            if(nums[i]>0){
                max[i]=Math.max(nums[i], max[i-1]*nums[i]);
                min[i]=Math.min(nums[i], min[i-1]*nums[i]);
            }else{
                max[i]=Math.max(nums[i], min[i-1]*nums[i]);
                min[i]=Math.min(nums[i], max[i-1]*nums[i]);
            }

            result = Math.max(result, max[i]);
        }

        return result;
    }
}

Reference

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