Leetcode: Maximum Product Subarray

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.

Understand the problem:
The problem is very similar to the maximum subarray, which calculates the maximum addition of a subarray. Unlike the in the maximum subarray problem the local optimal can lead to the global optimal, the maximum product subarray cannot. e.g. -2 3 -4, where at -4 the local max is -4, however the global should be -2 * 3 * -4. 

The solution is to maintain to dp arrays, one maintains the local min and the other maintain the local max. Therefore, we define the DP arrays as
dpMin[i], the minimum subarray INCLUDING nums[i]
dpMax[i], the maximum subarray INCLUDING nums[i]

dpMin[i] = Min(dpMin[i - 1] * A[i], dpMax[i - 1] * A[i], A[i]);
dpMax[i] = Max(dpMax[i - 1] * A[i], dp[Min[i - 1] * A[i], A[i]);

The final state is to check max(result, dpMax[i]). 

Code (Java):

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dpMin = new int[len];
        int[] dpMax = new int[len];
        
        dpMin[0] = nums[0];
        dpMax[0] = nums[0];
        
        for (int i = 1; i < len; i++) {
            dpMin[i] = Math.min(Math.min(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i]), nums[i]);
            dpMax[i] = Math.max(Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]);
        }
        
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, dpMax[i]);
        }
        
        return max;
    }
}

A constant space solution:
Note that dp[i] only relies on dp[i - 1], so we could just use two variables to solve the problem. 

Code (Java):

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int min = nums[0];
        int max = nums[0];
        
        int result = nums[0];
        
        for (int i = 1; i < len; i++) {
            
            int curMin = Math.min(Math.min(min * nums[i], max * nums[i]), nums[i]);
            int curMax = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            
            min = curMin;
            max = curMax;
            result = Math.max(result, max);
        }
        
        return result;
    }
}

Follow-up: 
How about the maximum product subsequence? For example, 2 -3 4, the result is 2 * 4 = 8

The solution would be very similar to the maximum product subarray. The only difference is max and min do not necessary include the nums[i]. Therefore, 
min = Min(min, min * nums[i], max * nums[i], nums[i]);
max = Max(max, max * nums[i], min * nums[i], nums[i]);
result = Max(result, max);