152. Maximum Product Subarray

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

🧠 Thuật Toán & Kỹ Thuật

Dynamic Programming (Quy hoạch động)
⏱️ Thời gian O(n×m)
💾 Không gian O(n×m)

💻 Lời Giải

C++ 0152-maximum-product-subarray.cpp 
class Solution {
public:
    int maxProduct(vector<int>& nums) {        
        int n = nums.size();
        int dp[n][2];
        dp[0][0] = dp[0][1] = nums[0];
        int ans = nums[0];
        
        for (int i = 1; i < n; ++i) {
            for (int state = 0; state <= 1; ++state) {
                ans = max({ans, nums[i], nums[i] * dp[i - 1][state]});
            }
            dp[i][0] = max({nums[i], nums[i] * dp[i - 1][1], nums[i] * dp[i - 1][0]});
            dp[i][1] = min({nums[i], nums[i] * dp[i - 1][1], nums[i] * dp[i - 1][0]});
        }
        
        return ans;
    }
};