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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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);