Given an integer array, nums, find a subarray that has the largest product, and return the product.

max-product-subarray.js

export function maxProduct(nums) {
  if (nums.length === 0) {
    return 0;
  }

  // we are going to track the minimum value as well as we progress
  // because we might encounter a negative value, and then another negative value
  // so it's possible our minimal value will be flipped to be a positive, and a new maximum

  // store here the max seen product so far
  let result = nums[0];

  // store min and max products at each iteration step
  let min = nums[0];
  let max = nums[0];

  for (let i = 1; i < nums.length; ++i) {
    // at each step, we are considering between 3 values
    // first, the value num itself
    // it's a valid product when we don't consider any elements left from it (so our possible subarray starts with num)
    // second, num * min, where min is the minimum product seen up to, but not including, num
    // third, num * max, where max is the max product seen up to, but not including, num
    // out of those 3 values, we choose min and max
    // new min is the min product seen up to and including num
    // new max is the max product seen up to and including num
    const num = nums[i];
    const minProd = num * min;
    const maxProd = num * max;
    min = Math.min(num, minProd, maxProd);
    max = Math.max(num, minProd, maxProd);
    result = Math.max(result, max);
  }
  return result;
}

// tc: O(n)
// sc: O(1)