Maximum Product Subarray | Leetcode

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

---

Solution: Use 1D dynamic programming, where max[i] is the maximum product ending at i, and min[i] is the minimum product ending at i.

max[i] = max(a[i], (max[i - 1] * a[i]), (min[i - 1] * a[i]))
min[i] = min(a[i], (max[i - 1] * a[i]), (min[i - 1] * a[i]))

We need min[i] because if a[i] is negative, then min[i] * a[i] would produce the biggest product.

public class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int curMax = max;
        int curMin = max;

        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];

            // We are changing curMax and curMin below,
            // so make sure to use the old value.
            int maxN = curMax * n;
            int minN = curMin * n;

            curMax = Math.max(Math.max(n, maxN), minN);
            curMin = Math.min(Math.min(n, minN), maxN);

            // Using "max = Math.max(max, curMax);"
            // here will exceed the leetcode time limit.
            if (curMax > max) max = curMax;
        }
        
        return max;
    }
}