Overview

Given an integer array, find the contiguous subarray (containing at least one number) that has the largest product, and return that product.

Implement maxProduct(nums).

Constraints

• Input is a non-empty array of integers (may include negatives and zero).
• The subarray must be contiguous (consecutive elements).
• The subarray must contain at least one element.
• Aim for $O(n)$ time complexity.
• Values can be negative — two negatives make a positive, so tracking both the running max and running min is essential.

Examples

maxProduct([2, 3, -2, 4]);     // 6  — subarray [2, 3]
maxProduct([-2, 0, -1]);       // 0  — subarray [0]
maxProduct([-2, 3, -4]);       // 24 — subarray [-2, 3, -4]
maxProduct([0, 2]);            // 2
maxProduct([-2]);              // -2

Notes

• This is a twist on the classic maximum subarray (Kadane's algorithm) — but you need to track both the current max and current min product at each step, because a negative value can flip a min into a max.
• At each element, the new max is the largest of: current * prevMax, current * prevMin, or current alone (start fresh).
• The global answer is the maximum of all per-step maxima.

Solution

function maxProduct(nums) {
  let globalMax = nums[0];
  let currentMax = nums[0];
  let currentMin = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const n = nums[i];
    const candidates = [n, n * currentMax, n * currentMin];
    currentMax = Math.max(...candidates);
    currentMin = Math.min(...candidates);
    globalMax = Math.max(globalMax, currentMax);
  }

  return globalMax;
}

Resources

• Maximum Product Subarray — LeetCode
• Kadane's Algorithm — Wikipedia