Maximum Product Subarray

January 10, 2025

Maximum Product Subarray Problem

Given an integer array nums, find the subarray with the maximum product and return its value.

A sub array is a continuous, non-empty portion of the array.

You can assume the result will fit within a 32-bit integer.

TOP 150 NOTOUT QUESTIONS
maximum product subarray problem

Constraints:

  • 1 <= nums.length <= 1000
  • -10 <= nums[i] <= 10

Maximum Product Subarray Solution

Approaches for solving Maximum Product Subarray problem

There are mainly 4 approach to solve this problem 

  1. Brute Force Method
  2. Sliding Window Method
  3. Kadane’s Algorithm Method
  4. Prefix & Suffix

1. Brute Force Method:

Check all possible subarrays in the array, calculate their products, and track the maximum product found. This method is simple but inefficient for large arrays as it checks every combination.

  • Time complexity: O(n^2)
  • Space complexity: O(1)

Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];

        for (int i = 0; i < nums.size(); i++) {
            int cur = nums[i];
            res = max(res, cur);
            for (int j = i + 1; j < nums.size(); j++) {
                cur *= nums[j];
                res = max(res, cur);
            }
        }
        
        return res;
    }
};

2. Sliding Window  Method

Use a sliding window to iterate through the array while keeping track of the current product, updating it as you move the window. This approach is faster but still needs care with negative numbers.

  • Time complexity: O(n)
  • Space complexity: O(n)

Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<vector<int>> A;
        vector<int> cur;
        int res = INT_MIN;
        for (auto& num : nums) {
            res = max(res, num);
            if (num == 0) {
                if (!cur.empty()) A.push_back(cur);
                cur.clear();
            } else cur.push_back(num);
        }
        if (!cur.empty()) {
            A.push_back(cur);
        }

        for (auto& sub : A) {
            int negs = 0;
            for (auto& i : sub) {
                if (i < 0) negs++;
            }

            int prod = 1;
            int need = (negs % 2 == 0) ? negs : (negs - 1);
            negs = 0;
            for (int i = 0, j = 0; i < sub.size(); i++) {
                prod *= sub[i];
                if (sub[i] < 0) { negs++; while (negs > need) {
                        prod /= sub[j];
                        if (sub[j] < 0) negs--;
                        j++;
                    }
                }
                if (j <= i) res = max(res, prod);
            }
        }
        return res;
    }
};

3. Kadane’s Algorithm

Modify Kadane’s algorithm to handle products by keeping track of both the maximum and minimum products at each index. This efficiently handles both positive and negative numbers.

  • Time complexity: O(n)
  • Space complexity: O(1)

Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int curMin = 1, curMax = 1;

        for (int num : nums) {
            int tmp = curMax * num;
            curMax = max(max(num * curMax, num * curMin), num);
            curMin = min(min(tmp, num * curMin), num);
            res = max(res, curMax);
        }
        return res;
    }
};

4. Prefix and Suffix Method

Precompute prefix and suffix products for the array, then find the maximum product by checking combinations of these values. This method reduces time complexity but uses extra space.

  • Time complexity: O(n)
  • Space complexity: O(1)

Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size(), res = nums[0];
        int prefix = 0, suffix = 0;

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

More Articles