https://leetcode.com/problems/maximum-product-subarray

maximumProductSubarray.js

/**
 * @param {number[]} nums
 * @return {number}
 */
/*
IDEA: 
- Do a prefix-multiply, i.e., a rolling product from left to
  right. 
- This strategy depends on the number of negative numbers in
  the input.
- With an even number of negatives, the largest product will
  just include as many numbers as possible. 
- Odd example: [1   ,-2  ,3  ,-4 , 5  ,-6  ]
               [1   ,-2  ,-6 ,24 , 120,-720] // left to right prefix-product
                                   ^ best answer is here
               [-720,-720,360,120,-30 ,-6  ] // right to left
                           ^ best answer is here
- With an odd number, we should do an extra pass from right 
  to left, to make sure we're considering both 'sides' of
  the input.
- 0 is a special case. If ever we see a  zero we should just
  start again. Otherwise the following should work:
  
*/
var maxProduct = function(nums) {
    
    if(!nums.length) return 0;
    if(nums.length === 1) return nums[0];
    
    let result = -Infinity;
    let product = 1;
    // Left to right pass
    for(let i=0; i<nums.length; i++){
        if(nums[i] === 0){ // if you see a zero, start again
            result = Math.max(result, 0);
            product = 1;
            continue;
        }else{ // otherwise do a rolling product
            product*=nums[i];
            result = Math.max(result, product); // and track the max
        }
    }
    
    // start again from right to left, in case the
    product = 1; // number of negatives is odd
    for(let i=nums.length-1; i>=0; i--){
        if(nums[i] === 0){ // if zero, start again
            result = Math.max(result, 0);
            product = 1;
            continue;
        }else{
            product*=nums[i]; // do a rolling product
            result = Math.max(result, product);
        }
    }
    
    return result;
};