Maximum Product Subarray

Maximum Product Subarray has a twist that trips up a lot of people. Negative numbers. Two negatives multiply into a positive. So the smallest product so far can suddenly become the biggest. The interviewer wants to see if you handle that. It is a small detail that changes the whole solution.

🎯 The Problem

You get an array of numbers. Find the contiguous run with the largest product.

• A subarray is a contiguous slice, with no gaps.
• You pick a start and an end and multiply everything between them.
• Return the largest product any slice can make.
• The numbers can be positive, negative, or zero.
• A zero resets the product. A negative can flip a small product into a large one.

Let us say the array is [2, 3, -2, 4]. The slice [2, 3] multiplies to 6. That is the biggest product you can get. The slice [2, 3, -2, 4] gives -48, which is much worse. So the answer is 6.

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

Explanation: the subarray [2, 3] has the largest product, 2 * 3 = 6

Here is the data. We are scanning for the slice with the biggest product.

🐢 Approach 1: Try Every Slice (Brute Force)

The idea in one line: multiply out every slice and keep the biggest product.

The idea:

• Pick a start position.
• Extend the end one step at a time.
• Multiply as you go.
• Keep the biggest product you ever see.

How it works:

• One loop picks the start.
• A second loop grows the slice to the right.
• Keep a running product and compare it with your best.

Why it is weak:

• You check every slice, and there are about n times n of them.
• That is O(n²) time.
• A big array makes this slow.

Here is the brute-force code for that idea:

def max_product(nums):
    best = nums[0]

    for start in range(len(nums)):
        product = 1
        for end in range(start, len(nums)):
            product *= nums[end]
            best = max(best, product)

    return best


print(max_product([2, 3, -2, 4]))

⚡ Approach 2: Track the Max and Min Together (Best)

The idea in one line: carry both the largest and smallest product ending here, because a negative flips them.

The idea:

• Keep two running products as you walk.
• The largest product ending at the current spot.
• The smallest product ending at the current spot.
• The smallest matters because of negatives. A very negative product becomes a big positive after another negative.

How it works:

• If the current number is negative, swap the running max and min.
• Set the new max to the larger of the number alone or the number times the old max.
• Set the new min to the smaller of the number alone or the number times the old min.
• The “number alone” option lets a zero or a fresh start break a bad streak.
• After each step, update the best answer with the running max.

Why it is fast:

• You touch each number once. That is O(n).
• You store only a few values. So the extra memory is O(1).

Here is a dry-run on [2, 3, -2, 4]. Watch the max and min as we go.

Steps to Solve

1. Set the running max, the running min, and the best answer all to the first number.
2. Walk through the array starting from the second number.
3. If the current number is negative, swap the running max and the running min.
4. Set the new running max to the larger of the number alone or the number times the running max.
5. Set the new running min to the smaller of the number alone or the number times the running min.
6. Update the best answer with the running max. Then return the best answer at the end.

#include <stdio.h>

int maxOf(int a, int b) { return a > b ? a : b; }
int minOf(int a, int b) { return a < b ? a : b; }

int maxProduct(int nums[], int n) {
    int best = nums[0];
    int curMax = nums[0];   // largest product ending here
    int curMin = nums[0];   // smallest product ending here
    for (int i = 1; i < n; i++) {
        int num = nums[i];
        if (num < 0) {       // negative flips max and min
            int tmp = curMax;
            curMax = curMin;
            curMin = tmp;
        }
        curMax = maxOf(num, curMax * num);   // best ending here
        curMin = minOf(num, curMin * num);   // worst ending here
        if (curMax > best) best = curMax;
    }
    return best;
}

int main(void) {
    int nums[] = {2, 3, -2, 4};
    int n = 4;
    printf("%d\n", maxProduct(nums, n));
    return 0;
}

6

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProduct(vector<int>& nums) {
    int best = nums[0];
    int curMax = nums[0];   // largest product ending here
    int curMin = nums[0];   // smallest product ending here
    for (int i = 1; i < (int)nums.size(); i++) {
        int num = nums[i];
        if (num < 0) swap(curMax, curMin);   // negative flips them
        curMax = max(num, curMax * num);     // best ending here
        curMin = min(num, curMin * num);     // worst ending here
        best = max(best, curMax);
    }
    return best;
}

int main() {
    vector<int> nums = {2, 3, -2, 4};
    cout << maxProduct(nums) << endl;
    return 0;
}

6

public class MaxProduct {
    public static int maxProduct(int[] nums) {
        int best = nums[0];
        int curMax = nums[0];   // largest product ending here
        int curMin = nums[0];   // smallest product ending here
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num < 0) {        // negative flips max and min
                int tmp = curMax;
                curMax = curMin;
                curMin = tmp;
            }
            curMax = Math.max(num, curMax * num);  // best ending here
            curMin = Math.min(num, curMin * num);  // worst ending here
            best = Math.max(best, curMax);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] nums = { 2, 3, -2, 4 };
        System.out.println(maxProduct(nums));
    }
}

6

def max_product(nums):
    best = nums[0]
    cur_max = nums[0]       # largest product ending here
    cur_min = nums[0]       # smallest product ending here
    for num in nums[1:]:
        if num < 0:                       # negative flips max and min
            cur_max, cur_min = cur_min, cur_max
        cur_max = max(num, cur_max * num)  # best ending here
        cur_min = min(num, cur_min * num)  # worst ending here
        best = max(best, cur_max)
    return best


nums = [2, 3, -2, 4]
print(max_product(nums))

6

function maxProduct(nums) {
  let best = nums[0];
  let curMax = nums[0]; // largest product ending here
  let curMin = nums[0]; // smallest product ending here
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    if (num < 0) {       // negative flips max and min
      [curMax, curMin] = [curMin, curMax];
    }
    curMax = Math.max(num, curMax * num);  // best ending here
    curMin = Math.min(num, curMin * num);  // worst ending here
    best = Math.max(best, curMax);
  }
  return best;
}

const nums = [2, 3, -2, 4];
console.log(maxProduct(nums));

6

Let us read the Python version line by line and explain why each line is there.

def max_product(nums):
    best = nums[0]
    cur_max = nums[0]
    cur_min = nums[0]
    for num in nums[1:]:
        if num < 0:
            cur_max, cur_min = cur_min, cur_max
        cur_max = max(num, cur_max * num)
        cur_min = min(num, cur_min * num)
        best = max(best, cur_max)
    return best

The lines best, cur_max, and cur_min all start at the first number. We have to seed them with a real value. The first element is the only slice we know about before the loop.

The line for num in nums[1:] walks through the rest of the array, starting from the second number. We already used the first number to seed our variables.

The line if num < 0 checks for a negative number. A negative flips the order. The largest product times a negative becomes the smallest. So cur_max, cur_min = cur_min, cur_max swaps them before we use them. This swap is the whole secret of the problem.

The line cur_max = max(num, cur_max * num) picks the best product ending at this spot. The option num alone matters. It lets us start fresh if the past product was bad, like after a zero.

The line cur_min = min(num, cur_min * num) does the mirror. It keeps the worst product ending here. We carry it because a future negative can turn it into the best.

The line best = max(best, cur_max) records the largest product we have seen anywhere so far. We check after every step, so we never miss the peak.

The final return best gives back the largest product across all slices.

⏱️ Time and Space Complexity

The brute force checks every slice, so it is slow. The min-and-max method scans the array once and stores only a few numbers. So it is fast and light. Tracking both the max and the min is what handles negatives correctly. That brings the time down to O(n) with O(1) extra space.

🧩 Key Takeaways

• ✅ Keep both the largest and the smallest product ending at each position.
• ✅ A negative number flips them, so swap the max and min before multiplying.
• ✅ Always compare against the number alone, so a zero can break a bad streak.
• ✅ Update the best answer after every step, so you never miss the peak.
• ✅ The whole thing runs in O(n) time and O(1) space.

🚀 What’s Next?

• Best Time to Buy and Sell Stock
• Product of Array Except Self