Maximum Product Subarray

NeetCode: Maximum Product Subarray · LeetCode: 152. Maximum Product Subarray · Difficulty: Medium

Given an integer array nums, return the largest product of any non-empty contiguous subarray. The result is guaranteed to fit in a 32-bit integer, and so does every prefix or suffix product, so int arithmetic never overflows here. Without that guarantee, int multiplication would wrap silently and long would be needed.

Example

Text

Input:  nums = [2, 3, -2, 4]    Output: 6     (subarray [2, 3])
Input:  nums = [-2, 0, -1]      Output: 0
Input:  nums = [-2, 3, -4]      Output: 24

Brute force: every subarray

Fix a start i, extend the end j one element at a time and keep a running product.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxProduct(new int[]{2, 3, -2, 4}));
        System.out.println(solution.maxProduct(new int[]{-2, 0, -1}));
        System.out.println(solution.maxProduct(new int[]{-2, 3, -4}));
        System.out.println(solution.maxProduct(new int[]{-2}));
    }
}

Output

Time: O(n^2). Space: O(1).

Optimal: track the best and worst product ending here

A negative number flips the order: the smallest (most negative) product so far becomes the largest after multiplying by another negative. So for each position keep two values, hi and lo, the maximum and minimum product of a subarray ending at this element. For a new x, the candidates are x alone (start fresh), hi * x and lo * x. A zero resets both, because x = 0 makes every candidate 0.

Java

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int hi = nums[0];
        int lo = nums[0];
        int best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            int a = hi * x;
            int b = lo * x;
            hi = Math.max(x, Math.max(a, b));
            lo = Math.min(x, Math.min(a, b));
            best = Math.max(best, hi);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxProduct(new int[]{2, 3, -2, 4}));
        System.out.println(solution.maxProduct(new int[]{-2, 0, -1}));
        System.out.println(solution.maxProduct(new int[]{-2, 3, -4}));
        System.out.println(solution.maxProduct(new int[]{-2}));
    }
}

Output

Time: O(n). Space: O(1). For [-2, 3, -4]: after -2 (hi=lo=-2), after 3 (hi=3, lo=-6), after -4 (hi=max(-4, -12, 24)=24).