/**
* 152. Maximum Product Subarray
* Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
*
* It is guaranteed that the answer will fit in a 32-bit integer.
*
* A subarray is a contiguous subsequence of the array.
* 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.
*
*/
See the solution at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/MaxProductSubArray.java
Observation: Need to iterate on the array while tracking the max and min numbers found so far. Min because multiple of two negatives is a positive. Calculate prior max as max(priormax * current , priorMin*current), calculate prior min as min(priormin*current, priormax*current). Its also possible that the current number itself is max or min so far, so need to check for that. In the end we return max number so far found.
Here is the code:
public int maxProduct(int[] nums) {
int priorMin = 1;
int priorMax = 1;
for (int j =0; j < nums.length; j++) {
int max = Math.max(nums[j] * priorMax, nums[j] * priorMin);
int min = Math.min(nums[j] * priorMax, nums[j] * priorMin);
priorMax = Math.max(nums[j] , max);
priorMin = Math.min(nums[j] , min);
this.maxSubArr = Math.max(priorMax, this.maxSubArr);
}
return this.maxSubArr;
}