Leetcode - 152. Maximum Product Subarray

문제

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

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

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

아이디어

현재 값, 현재까지 곱중에 가장 큰값, 현재까지 곱중에 가장 작은값 이 세가지를 순서대로 계산하면서 앞으로 나아간다. (해설참고) 가장 큰 값은 절대값이 가장 큰 두 음수 값의 곱이 될 수 도 있으므로, 최소 작은값도 가지고 있어야 하는것.

아래 예시에서는 답이 96이 된다.

num[i]       2  3 -2   4  -2
max so far   2  6 -6  -24 96
min so far   2  3 -12 -48 48

해결 O(n)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max_so_far = nums[0];
        int min_so_far = nums[0];
        int final_max = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            int saved_max_so_far = max_so_far; 
            max_so_far = std::max({nums[i], nums[i] * max_so_far, nums[i] * min_so_far});
            min_so_far = std::min({nums[i], nums[i] * saved_max_so_far, nums[i] * min_so_far}); // need to use max_so_far of previous version
            //printf("(%d,%d)", max_so_far, min_so_far);
            final_max = std::max(final_max, max_so_far);
        }
        return final_max;
    }
};

230206 다시 풀어봄

지난번에 배웠던 해결방법을 떠올리지 못했음. ㅜㅜ

class Solution {
public:
    // 2 3 -2 4 -1
    int maxProduct(vector<int>& nums) {
        vector<int> maxsofar(nums.size(), 0);
        vector<int> minsofar(nums.size(), 0);
        int maxval = nums[0];
        maxsofar[0] = nums[0];
        minsofar[0] = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            int val1 = maxsofar[i-1] * nums[i];
            int val2 = minsofar[i-1] * nums[i];
            maxsofar[i] = std::max(nums[i], std::max(val1, val2));
            minsofar[i] = std::min(nums[i], std::min(val1, val2));
            maxval = std::max(maxval, maxsofar[i]);
        }
        return maxval;
    }
};