[leetcode 152] Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

연속 곱중에 가장 큰 곱을 리턴하라.

Example 1:

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

Example 2:

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

 

 

풀이:

- dp이자 그리디 스러운 문제이다.

- 음수가 있어서 어려웠던 문제! 블로그를 참고해서 풀었다.

- 항상 이런 문제는 현재의 시점을 잘 파악해줘야 한다. 변수가 현재 값을 포함하여 곱했을 때를 따져줘야 한다. 자꾸 현재 값을 포함한 최댓값과 전체 배열에서의 최대값을 헷갈리는 듯 하다 ㅠ

- 핵심: 음수가 있으므로 최솟값 역시 저장해줘야 한다. 음수 양수 음수의 곱은 양수가 되기 때문이다. 

현재값(nums[i]과

현재 최댓값: 현재값을 포함하여 곱했을 때 나올수 있는 최댓값 -> 1을 곱함, 이전까지 나온 양수를 곱함, 이전까지 나온 음수를 곱함 이렇게 3가지 경우에서 최대를 골라줌.

현재 최솟값: 현재값을 포함하여 곱했을 때 나올 수 있는 최솟값

을 비교해서 업데이트 해준다.

 

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int result = nums[0];
        int maxPrev = nums[0], minPrev = nums[0];
        int n = nums.size();
        
        for(int i=1; i<n; i++){
            int tmp = maxPrev;
            maxPrev = max(max(maxPrev*nums[i], minPrev*nums[i]), nums[i]);
            minPrev = min(min(tmp*nums[i], minPrev*nums[i]), nums[i]);
            result = max(result, maxPrev);
        }
        
        return result;
    }
};