MAXIMUM PRODUCT SUBARRAY

Practice Link

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.

Brute Force#

The simplest approach tries every possible subarray by fixing a start index and extending the end index while accumulating the product. This guarantees we check all candidates but performs redundant multiplications, leading to O(n²) time.

• Generate all subarrays by fixing start index i and extending end index j.
• Track the running product and update the global maximum at each step.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxi = INT_MIN;
        for(int i=0;i<nums.size();i++)
        {
            int p = nums[i];
            for(int j=i+1;j<nums.size();j++)
            {
                maxi = max(p, maxi);
                p *= nums[j];
            }
            maxi = max(p, maxi);
        }
        
        return maxi;
    }
};

Time Complexity: O(n^2), --> TLE

Space Complexity: O(1),

Prefix & Suffix Product Traversal#

This approach handles 0s and negatives

• We cannot just do a forward pass because negatives can turn small values into large ones (e.g., -2 * -3 = 6).
• Zeroes break the product chain. So any product that hits zero should reset.
• Instead of tracking max/min at every step like DP, we can:
  • Traverse left to right (prefix).
  • Traverse right to left (suffix).
  • Take the maximum of all these values.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();

        int prefix=1, suffix=1, maxiP = INT_MIN;

        for(int i=0;i<n;i++)
        { 
            prefix = (prefix==0 ? 1 : prefix) * nums[i];
            suffix = (suffix==0 ? 1 : suffix) * nums[n-i-1];
            maxiP = max({prefix, suffix, maxiP});
        }
        return maxiP;
    }
};

Time Complexity: O(n),

Space Complexity: O(1),

DP solution#

The key insight is that a negative number can flip a very small (negative) product into a very large positive one. So at every index, we need to track both the maximum and minimum products ending at that index — because the current minimum (most negative) might become the maximum when multiplied by a negative number. This dual tracking eliminates the prefix/suffix pass and handles all edge cases in a single forward scan.

• currMax: maximum product of the subarray ending at the current index
• currMin: minimum product of the subarray ending at the current index (needed to handle negative × negative = positive)
• maxProduct: the overall maximum product seen so far

At each step, currMax and currMin are computed from three candidates: nums[i] alone (start fresh), nums[i] * currMax, and nums[i] * currMin.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();

        int currMax= nums[0], currMin=nums[0], maxiP = nums[0];

        for(int i=1;i<n;i++)
        { 
            int temp = max({nums[i], nums[i]*currMax, nums[i]*currMin});
            currMin = min({nums[i], nums[i]*currMax, nums[i]*currMin});
            currMax = temp;
            maxiP = max(currMax, maxiP);
        }
        return maxiP;
    }
};

Time Complexity: O(n),

Space Complexity: O(1),