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.
Note that the product of an array with a single element is the value of that element.
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 subarray of
nums is guaranteed to fit in a 32-bit integer.
Solutions
Solution 1
PythonJavaC++GoTypeScriptRustJavaScriptC#
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
/**
* @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;
};(code-box)
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;
}
}(code-box)
