[Leetcode] 152. Maximum Product Subarray (C++)

문제

152. Maximum Product Subarray

코드

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int m = 0, M = 0, cur = 0;
        
        m = M = cur = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > 0){
                M = max(M * nums[i], nums[i]);
                m = min(m * nums[i], nums[i]);
            }   
            else {
                int temp = max(m * nums[i], nums[i]);
                m = min(nums[i] * M, nums[i]);
                M = temp;
            }
            cur = max(cur, M);
        }
        return cur;
    }
};

접근

배열에 들어있는 값이 음수도 있고 최대 값이 음수가 없으리란 보장이 없다. 따라서 현재 보는 원소가 음수인지 양수인지 나누어야한다고 생각했다. 또한 음수가 나온 경우 최소 값과 곱하여 최대가 될 수 있기 때문에 최대 값 뿐만 아니라 최소 값도 유지하였다. 양수가 나오면 유지하는 최대 값과 최소 값을 이용해 각자 값을 갱신하였고 음수인 경우 최대와 곱해야 최소가 될 수 있기 때문에 반대로 바꿔서 계산하였다. 매 반복이 끝날 때마다 최대 값을 cur에 저장하였다.