Algorithm
Problem Name: 152. Maximum Product Subarray
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
numsis guaranteed to fit in a 32-bit integer.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int maxProduct(int A[], int n) {
int i;
int min, max, ret;
ret = max = min = A[0];
for (i = 1; i < n; i++) {
int t_max = max;
if (max * A[i] > A[i])
max *= A[i];
else
max = A[i];
/* A[i] is negative*/
if (min * A[i] > max)
max = min * A[i];
if (min * A[i] < A[i])
min *= A[i];
else
min = A[i];
/* A[i] is negative*/
if (t_max * A[i] < min)
min = t_max * A[i];
if (max > ret)
ret = max;
}
return ret;
}
int main() {
int A[] = {1, -2, 3, -2, -3};
printf("%d\n", maxProduct(A, 5));
return 0;
}
Input
nums = [2,3,-2,4]
Output
6
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int maxProduct(int[] nums) {
int currMax = nums[0];
int currMin = nums[0];
int maxProd = currMax;
for (int i = 1; i < nums.length; i++) {
int temp = currMax;
currMax = Math.max(Math.max(temp * nums[i], currMin * nums[i]), nums[i]);
currMin = Math.min(Math.min(temp * nums[i], currMin * nums[i]), nums[i]);
maxProd = Math.max(maxProd, currMax);
}
return maxProd;
}
}
Input
nums = [2,3,-2,4]
Output
6
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const maxProduct = function(nums) {
let min = nums[0], max = nums[0], res = nums[0]
for(let i = 1, n = nums.length; i < n; i++) {
const e = nums[i]
if(e < 0) [min, max] = [max, min]
min = Math.min(e, min * e)
max = Math.max(e, max * e)
res = Math.max(res, max>
}
return res
};
Input
nums = [-2,0,-1]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxProduct(self, nums):
res, min_pos, max_neg, cur = -float("inf"), float("inf"), -float("inf"), 1
for num in nums:
cur *= num
if cur > res: res = cur
elif 0 < cur // min_pos > res: res = cur // min_pos
elif 0 < cur // max_neg > res: res = cur // max_neg
if cur == 0: min_pos, max_neg, cur = float("inf"), -float("inf"), 1
elif max_neg < cur < 0: max_neg = cur
elif 0 < cur < min_pos: min_pos = cur
return res
Input
nums = [-2,0,-1]
#5 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0152_MaximumProductSubarray
{
public int MaxProduct(int[] nums)
{
if (nums == null || nums.Length == 0) return 0;
int minProduct = 1, maxProduct = 1, result = int.MinValue;
foreach (var num in nums)
{
if (num < 0)
{
var temp = minProduct;
minProduct = maxProduct;
maxProduct = temp;
}
minProduct = Math.Min(num, minProduct * num);
maxProduct = Math.Max(num, maxProduct * num);
result = Math.Max(result, maxProduct);
}
return result;
}
}
}
Input
nums = [2,3,-2,4]
Output
6