Maximum Product Subarray — C++ Coding Problem
Difficulty: medium | Category: dynamic-programming
Problem Description
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. Hint: Track both the maximum and minimum product ending at each position — a negative minimum can become the new maximum when multiplied by another negative.
Examples
Example 1
Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: Subarray [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 contiguous subarray.
Example 3
Input: nums = [-2, 3, -4]
Output: 24