Leetcode 152 Solution

This article provides solution to leetcode question 152 (maximum-product-subarray)
Categories:
Tags:
Access this page by simply typing in "lcs 152" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> dp1(nums.size());
        vector<int> dp2(nums.size());

        int max_product = INT_MIN;

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

            max_product = max(dp1[i], max_product);
        }

        return max_product;
    }
};