Coding

Maximum Product Subarray in an Array

Asked at

Cisco Meraki

Microsoft

PhonePe

Visa

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array nums. Find the **subarray **with the largest product, and return the **product **of the elements present in that subarray.

A **subarray **is a **contiguous **non-empty **sequence **of elements within an array.

Input: nums = [4, 5, 3, 7, 1, 2] Output: 840 Explanation: The largest product is given by the whole array itself

Input: nums = [-5, 0, -2] Output: 0 Explanation: The largest product is achieved with the following subarrays [0], [-5, 0], [0, -2], [-5, 0, -2].

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

1 <= nums.length <= 104
-10 <= nums[i] <= 10
-109 <= product of any prefix or suffix of nums <= 109

cpp

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        
    }
};

java

class Solution {
    public int maxProduct(int[] nums) {
        
    }
}

python

class Solution:
    def maxProduct(self, nums):

javascript

class Solution {
    maxProduct(nums) {

    }
}

csharp

public class Solution
{
    public int MaxProduct(List<int> nums)
    {
        
    }
}

func maxProduct(nums []int) int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Track both the maximum and minimum product of a non-empty subarray ending at the current index.
02For each value, compare starting fresh with extending the previous maximum or minimum.
03Update the global answer from the new ending maximum.
04Explain how zeros reset the running states and negatives swap their roles.

Reference answer

For sums, one running maximum is enough. For products, a large negative minimum can become the largest positive value after multiplication by a negative number, so track both extremes.

Initialize currentMax, currentMin, and answer to the first element. For each later value x, compute the three candidates x, x * previousMax, and x * previousMin. The new currentMax is their maximum and the new currentMin is their minimum. Update answer with currentMax. Using saved previous values is important so one update does not contaminate the other. An equivalent implementation swaps currentMax and currentMin when x is negative, then updates both.

Including x by itself naturally restarts the subarray after a zero or after an unhelpful prefix. The states always describe non-empty subarrays ending exactly at the current position, and the global answer considers every possible end. Time is O(n) and extra space is O(1). Initialize from the array rather than zero so all-negative single-element cases remain valid.

Then expect these follow-ups

How would you also return the boundaries of the optimal subarray?
Tests: state reconstruction
Why is tracking the minimum product necessary?
Tests: invariant understanding

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question