Question

152. Maximum Product Subarray

中文文档

Description

Given an integer array nums, find a subarray 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.

 

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

Solution 1

class Solution:
  def maxProduct(self, nums: List[int]) -> int:
    ans = f = g = nums[0]
    for x in nums[1:]:
      ff, gg = f, g
      f = max(x, ff * x, gg * x)
      g = min(x, ff * x, gg * x)
      ans = max(ans, f)
    return ans

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;
  }
}

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

func maxProduct(nums []int) int {
  f, g, ans := nums[0], nums[0], nums[0]
  for _, x := range nums[1:] {
    ff, gg := f, g
    f = max(x, max(ff*x, gg*x))
    g = min(x, min(ff*x, gg*x))
    ans = max(ans, f)
  }
  return ans
}

function maxProduct(nums: number[]): number {
  let [f, g, ans] = [nums[0], nums[0], nums[0]];
  for (let i = 1; i < nums.length; ++i) {
    const [ff, gg] = [f, g];
    f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
    g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
    ans = Math.max(ans, f);
  }
  return ans;
}

impl Solution {
  pub fn max_product(nums: Vec<i32>) -> i32 {
    let mut f = nums[0];
    let mut g = nums[0];
    let mut ans = nums[0];
    for &x in nums.iter().skip(1) {
      let (ff, gg) = (f, g);
      f = x.max(x * ff).max(x * gg);
      g = x.min(x * ff).min(x * gg);
      ans = ans.max(f);
    }
    ans
  }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  let [f, g, ans] = [nums[0], nums[0], nums[0]];
  for (let i = 1; i < nums.length; ++i) {
    const [ff, gg] = [f, g];
    f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
    g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
    ans = Math.max(ans, f);
  }
  return ans;
};

public 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;
  }
}