[Dynamic Programming][Medium] 152. Maximum Product Subarray

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

 

Q. 정수배열 nums가 주어질 때, sub array 중 곱이 가장 큰 값을 찾아라.

 

Solution. 

 우선 간단하게 2중 배열로 접근해 본다. 

 

 시작과 끝을 지정하고 

 과정 중 가장 큰 값만을 기억해서 반환한다. 

 

int maxProduct(vector<int>& nums) 
{
    int ret = INT_MIN;
    for(int left = 0; left < nums.size(); ++left)
    {
        int cur = nums[left];
        ret = max(ret, cur);
        for(int right = left+1; right < nums.size(); ++right)
        {
            cur *= nums[right];
            ret = max(ret, cur);
        }
    }
    return ret;
}

 

하지만 성능이 좋지 않다. 

문제에서 원하는 해결책이 아니다. 

 

 

찾아보니 이런경우, 최적 알고리즘이 있다. 

Kadane's Algorithm이라고 한다. 

 

곱의 특성을 활용하여 현재값이 음수이면, 과정 최대, 최소를 바꾸고 

현재값과 누적 곱중, 최대 최소 값을 저장한다. 

그 최대값에서 최대값을 찾는다.

int maxProduct(vector<int>& nums) 
{
    int ret = nums[0];
    int curMin = ret;
    int curMax = ret;

    for(int left = 1; left < nums.size(); ++left)
    {
        int cur = nums[left];
        if(cur < 0) swap(curMin, curMax);

        curMin = min(cur, cur*curMin);
        curMax = max(cur, cur*curMax);

        ret = max(ret, curMax);
    }
    return ret;
}

 

성능은 확실해 보인다. 

 

Note) 이 풀이법은 암기 해 두는 것이 좋을 듯 하다.