152. Maximum Product Subarray

Question

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.

Algorithm

1. The Constrains is a little misleading, making me think it may leverage prefix products;
2. A tricky way in my view, leverage dynamic programming.
3. Maintain the max so far and min so far, each number next can be
   1. the largest, or
   2. multiply max
      1. be the max
      2. or min,
   3. Miltiply min
      1. Be the max
      2. Or min
4. By loop all the elements in one pass we get the max.

Code

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            max = Math.max(nums[i], Math.max(nums[i] * max, nums[i] * min));
            min = Math.min(nums[i], Math.min(nums[i] * temp, nums[i] * min));
            res = Math.max(res, max);
        }
        return res;
    }
}