Maximum Product Subarray

Problem

Given an integer array nums, return the largest product of any contiguous subarray.

Constraints

• 1 ≤ nums.length ≤ 2·10⁴
• −10 ≤ nums[i] ≤ 10

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def maxProduct(self, nums):
        best = cur_max = cur_min = nums[0]
        for x in nums[1:]:
            if x < 0:
                cur_max, cur_min = cur_min, cur_max
            cur_max = max(x, cur_max * x)
            cur_min = min(x, cur_min * x)
            best = max(best, cur_max)
        return best

Java

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            int prevMax = max, prevMin = min;
            max = Math.max(n, Math.max(prevMax * n, prevMin * n));
            min = Math.min(n, Math.min(prevMax * n, prevMin * n));
            best = Math.max(best, max);
        }
        return best;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.