LeetCode Hot 100 P152 Maximum Product Subarray

---

Timeline

Timeline

2026-03-21

init

Dynamic Programming

---

Problem:

P152 Maximum Product Subarray

https://leetcode.cn/problems/maximum-product-subarray/description/?envType=study-plan-v2&envId=top-100-liked

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        int maxProduct(vector<int> &nums)
        {
                int i, n = nums.size();
                int max_val = nums[0];
                // dp[i][0] represents the non-empty contiguous subarray ending with nums[i] that has the maximum product
                // dp[i][1] represents the non-empty contiguous subarray ending with nums[i] that has the minimum product
                // dp[i][0] = max{ dp[i-1][0] * nums[i],dp[i-1][1] *nums[i] , nums[i]}
                // dp[i][1] = min{ dp[i-1][0] * nums[i],dp[i-1][1] *nums[i] , nums[i]}

                vector<vector<int> > dp(n, vector<int>(2));

                dp[0][0] = nums[0];
                dp[0][1] = nums[0];

                for (i = 1; i < n; i++) {
                        dp[i][0] = std::max(
                                { dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i], nums[i] });
                        dp[i][1] = std::min(
                                { dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i], nums[i] });
                        max_val = std::max(max_val, dp[i][0]);
                }
                return max_val;
        }
};