Maximum Product Subarray - Practice Coding Problems

Maximum Product Subarray - Problem

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.

Note: The product of an array with a single element is the value of that element.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: The subarray [2,3] has the largest product 6.

Example 2 — All Negative

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

› Output: 0

💡 Note: The result cannot be 2, because [-2,-1] is not a subarray.

Example 3 — Single Element

$ Input: nums = [-2]

› Output: -2

💡 Note: Single element subarray has product -2.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with positive and negative numbers

Find Subarrays

Consider all contiguous subarrays

Maximum Product

Return the largest product found

Key Takeaway

🎯 Key Insight: Negative numbers can flip small products into large ones, so we must track both maximum and minimum products at each position

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is that negative numbers can turn small products into large ones. The optimal approach uses dynamic programming to track both maximum and minimum products at each position, swapping them when encountering negative numbers. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all possible subarrays and find maximum product
Dynamic Programming	O(n)	O(1)	Track both maximum and minimum products at each position

Brute Force — Algorithm Steps

Iterate through each starting position
For each start, iterate through all ending positions
Calculate product of current subarray
Update maximum product if current is larger

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Calculate Products

Find product for each subarray

Track Maximum

Keep the largest product found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int maxProduct = nums[0];
    
    for (int i = 0; i < numsSize; i++) {
        int currentProduct = 1;
        for (int j = i; j < numsSize; j++) {
            currentProduct *= nums[j];
            if (currentProduct > maxProduct) {
                maxProduct = currentProduct;
            }
        }
    }
    
    return maxProduct;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* ptr = line + 1;
    
    while (*ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        int num = 0;
        int sign = 1;
        if (*ptr == '-') {
            sign = -1;
            ptr++;
        }
        while (*ptr >= '0' && *ptr <= '9') {
            num = num * 10 + (*ptr - '0');
            ptr++;
        }
        nums[count++] = num * sign;
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops iterate through all possible subarrays

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track max product and current product

✓ Linear Space

67.5K Views

High Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler