Explorer
Data Structures & Algorithms

Find the contiguous subarray within an array which has the largest product.

Problem Statement

Given an integer array `nums`, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.

Examples

Input: nums = [2, 3, -2, 4]

Output: 6

Explanation: [2, 3] has the largest product 6.

Input: nums = [-2, 0, -1]

Output: 0

Explanation: Combining the input according to Maximum Product Subarray in an Array logic yields 0.

Input: nums = [-2, 3, -4]

Output: 24

Explanation: Combining the input according to Maximum Product Subarray in an Array logic yields 24.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: Because multiplying two negative numbers creates a positive product, track both the minimum product and maximum product ending at each position. šŸ’” Hint 2: When nums[i] is negative, swap max and min before computing. šŸ’” Hint 3: max = Math.max(num, max * num) and min = Math.min(num, min * num).

Editorial & Approach

Problem Overview & Intuition

A negative number multiplied by the minimum (most negative) product becomes a large positive number. Therefore, maintaining both the current maximum and minimum products ending at position i allows O(N) time and O(1) space.

Step-by-Step Approach

  1. Initialize max = nums[0], min = nums[0], result = nums[0].
  2. Iterate i from 1 to nums.length - 1.
  3. If nums[i] < 0, swap max and min.
  4. Update max = Math.max(nums[i], max * nums[i]).
  5. Update min = Math.min(nums[i], min * nums[i]).
  6. Update result = Math.max(result, max).
  7. Return result.

Optimal Implementation (JavaScript)

function maxProduct(nums) {
  let max = nums[0], min = nums[0], result = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    if (num < 0) {
      const temp = max;
      max = min;
      min = temp;
    }
    max = Math.max(num, max * num);
    min = Math.min(num, min * num);
    result = Math.max(result, max);
  }
  return result;
}

Complexity Analysis

Time Complexity O(N) ā€” single pass through the array.
Space Complexity O(1) ā€” constant extra variables.

Edge Cases & Corner Traps Handled

  • Array with zeroes: resets current product.
  • All negative numbers.
  • Single element array.

Maximum Product Subarray in an Array

Hard
Given an integer array `nums`, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.
Example Scenarios
1Example 1
Input: nums = [2, 3, -2, 4]
Output: 6
Explanation:

[2, 3] has the largest product 6.

2Example 2
Input: nums = [-2, 0, -1]
Output: 0
Explanation:

Combining the input according to Maximum Product Subarray in an Array logic yields 0.

3Example 3
Input: nums = [-2, 3, -4]
Output: 24
Explanation:

Combining the input according to Maximum Product Subarray in an Array logic yields 24.

Editor
Loading Editor...
nums =
[2, 3, -2, 4]
Output:Click "Run" above to execute and verify your code here.
6