medium1D Dynamic Programming

Maximum Product Subarray

Find the largest product of a nonempty contiguous subarray. Inputs and all products fit in a signed 64-bit integer.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated integers on line 1.

Expected result

The maximum product.

Case 1

Input

2 3 -2 4

Expected output

Case 2

Input

-2 3 -4

Expected output

Case 3

Input

-2 0 -1

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Kadane works for sums; products flip when a negative appears, and a zero resets the run. n ≤ 2 × 10^4. Keep the max and min product ending here; the new value may multiply either or start a new segment. The answer is the best max seen.

class Solution {
    public int maxProduct(int[] nums) {
        int f = nums[0], g = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int ff = f, gg = g;
            f = Math.max(nums[i], Math.max(ff * nums[i], gg * nums[i]));
            g = Math.min(nums[i], Math.min(ff * nums[i], gg * nums[i]));
            ans = Math.max(ans, f);
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.