Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• C#
• RenderScript

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

• 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
  
  

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

• /**
   * @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;
      }
  }
  

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

All Problems

All Solutions