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 subarray 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
|
1
2
3
4
5
6
7
8
9
10
11
12 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | 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 *
|