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.
Examples:
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.Solution in Python
Python
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
# Initialize the variables to store the maximum and minimum products up to the current position
current_max = current_min = max_product = nums[0]
# Iterate through the array starting from the second element
for num in nums[1:]:
# If the current number is negative, swapping the current max and min helps manage the sign change
if num < 0:
current_max, current_min = current_min, current_max
# Calculate the maximum product up to the current position
current_max = max(num, current_max * num)
# Calculate the minimum product up to the current position
current_min = min(num, current_min * num)
# Update the global maximum product
max_product = max(max_product, current_max)
return max_productExplanation:
- Initialization:
current_maxandcurrent_minare initialized to the first element of the array. They represent the maximum and minimum products of subarrays ending at the current position.max_productis initialized to the first element, representing the maximum product found so far.
- Iteration:
- We iterate through the array starting from the second element.
- If the current number (
num) is negative, we swapcurrent_maxandcurrent_min. This is because multiplying by a negative number flips the signs, and what was previously the maximum could become the minimum and vice versa.
- Update
current_maxandcurrent_min:current_maxis updated to be the maximum of the current number itself or the product ofcurrent_maxand the current number.current_minis updated to be the minimum of the current number itself or the product ofcurrent_minand the current number.
- Update
max_product:max_productis updated to be the maximum value between itself andcurrent_max.
- Return the Result:
- Finally, we return
max_product, which holds the largest product of any subarray within the input array.
- Finally, we return
This approach ensures that we consider all possible subarrays efficiently with a time complexity of O(n).
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
if (nums.length === 0) {
return 0;
}
// Initialize the variables to store the maximum and minimum products up to the current position
let currentMax = nums[0];
let currentMin = nums[0];
let maxProduct = nums[0];
// Iterate through the array starting from the second element
for (let i = 1; i < nums.length; i++) {
let num = nums[i];
// If the current number is negative, swapping the current max and min helps manage the sign change
if (num < 0) {
[currentMax, currentMin] = [currentMin, currentMax];
}
// Calculate the maximum product up to the current position
currentMax = Math.max(num, currentMax * num);
// Calculate the minimum product up to the current position
currentMin = Math.min(num, currentMin * num);
// Update the global maximum product
maxProduct = Math.max(maxProduct, currentMax);
}
return maxProduct;
};Solution in Java
Java
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) {
return 0;
}
// Initialize the variables to store the maximum and minimum products up to the current position
int currentMax = nums[0];
int currentMin = nums[0];
int maxProduct = nums[0];
// Iterate through the array starting from the second element
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
// If the current number is negative, swapping the current max and min helps manage the sign change
if (num < 0) {
int temp = currentMax;
currentMax = currentMin;
currentMin = temp;
}
// Calculate the maximum product up to the current position
currentMax = Math.max(num, currentMax * num);
// Calculate the minimum product up to the current position
currentMin = Math.min(num, currentMin * num);
// Update the global maximum product
maxProduct = Math.max(maxProduct, currentMax);
}
return maxProduct;
}
}Solution in C#
C#
public class Solution {
public int MaxProduct(int[] nums) {
if (nums.Length == 0) {
return 0;
}
// Initialize the variables to store the maximum and minimum products up to the current position
int currentMax = nums[0];
int currentMin = nums[0];
int maxProduct = nums[0];
// Iterate through the array starting from the second element
for (int i = 1; i < nums.Length; i++) {
int num = nums[i];
// If the current number is negative, swapping the current max and min helps manage the sign change
if (num < 0) {
int temp = currentMax;
currentMax = currentMin;
currentMin = temp;
}
// Calculate the maximum product up to the current position
currentMax = Math.Max(num, currentMax * num);
// Calculate the minimum product up to the current position
currentMin = Math.Min(num, currentMin * num);
// Update the global maximum product
maxProduct = Math.Max(maxProduct, currentMax);
}
return maxProduct;
}
}