README_EN.md

152. Maximum Product Subarray

中文文档

Description

Given an integer array nums, find a contiguous non-empty subarray within the array 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.

A subarray is a contiguous subsequence of the array.

 

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

 

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solutions

Python3

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxf = minf = res = nums[0]
        for num in nums[1:]:
            m, n = maxf, minf
            maxf = max(num, m * num, n * num)
            minf = min(num, m * num, n * num)
            res = max(res, maxf)
        return res

Java

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

TypeScript

function maxProduct(nums: number[]): number {
    let n = nums.length;
    let preMax = nums[0],
        preMin = nums[0],
        ans = nums[0];
    for (let i = 1; i < n; ++i) {
        let cur = nums[i];
        let x = preMax,
            y = preMin;
        preMax = Math.max(x * cur, y * cur, cur);
        preMin = Math.min(x * cur, y * cur, cur);
        ans = Math.max(preMax, ans);
    }
    return ans;
}

C#

public class Solution {
    public int MaxProduct(int[] nums) {
        int maxf = nums[0], minf = nums[0], res = nums[0];
        for (int i = 1; i < nums.Length; ++i)
        {
            int m = maxf, n = minf;
            maxf = Math.Max(nums[i], Math.Max(nums[i] * m, nums[i] * n));
            minf = Math.Min(nums[i], Math.Min(nums[i] * m, nums[i] * n));
            res = Math.Max(res, maxf);
        }
        return res;
    }
}

C++

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxf = nums[0], minf = nums[0], res = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int m = maxf, n = minf;
            maxf = max(nums[i], max(nums[i] * m, nums[i] * n));
            minf = min(nums[i], min(nums[i] * m, nums[i] * n));
            res = max(res, maxf);
        }
        return res;
    }
};

Go

func maxProduct(nums []int) int {
	maxf, minf, res := nums[0], nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		m, n := maxf, minf
		maxf = max(nums[i], max(nums[i]*m, nums[i]*n))
		minf = min(nums[i], min(nums[i]*m, nums[i]*n))
		res = max(res, maxf)
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Rust

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut min = nums[0];
        let mut max = nums[0];
        let mut res = nums[0];
        for &num in nums.iter().skip(1) {
            let (pre_min, pre_max) = (min, max);
            min = num.min(num * pre_min).min(num * pre_max);
            max = num.max(num * pre_min).max(num * pre_max);
            res = res.max(max);
        }
        res
    }
}

...