152. Maximum Product Subarray
給定一個整數數組 nums，找到具有最大乘積的子數組，並返回該乘積。
測試用例的生成保證答案將適合32位整數。
範例 :
輸入: nums = [2,3,-2,4] 輸出: 6 說明: [2,3] 具有最大的乘積 6。
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 product up to the current position
max_product = min_product = result = nums[0]
# Iterate through the array, starting from the second element
for num in nums[1:]:
if num < 0:
# Swap max and min when a negative number is encountered
max_product, min_product = min_product, max_product
# Update the maximum and minimum product up to the current position
max_product = max(num, max_product * num)
min_product = min(num, min_product * num)
# Update the result with the maximum product found so far
result = max(result, max_product)
return result
17.01MB, 91ms
C++
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int maxProduct(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int max_product = nums[0];
int min_product = nums[0];
int result = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
if (nums[i] < 0) {
swap(max_product, min_product);
}
max_product = max({nums[i], static_cast<int>(static_cast<long long>(max_product) * nums[i])});
min_product = min({nums[i], static_cast<int>(static_cast<long long>(min_product) * nums[i])});
result = max(result, max_product);
}
return result;
}
};
16.35MB, 4ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
if (nums.length === 0) {
return 0;
}
let maxProduct = nums[0];
let minProduct = nums[0];
let result = nums[0];
for (let i = 1; i < nums.length; i++) {
let num = nums[i];
if (num < 0) {
// Swap maxProduct and minProduct when a negative number is encountered
[maxProduct, minProduct] = [minProduct, maxProduct];
}
// Update the maximum and minimum product up to the current position
maxProduct = Math.max(num, maxProduct * num);
minProduct = Math.min(num, minProduct * num);
// Update the result with the maximum product found so far
result = Math.max(result, maxProduct);
}
return result;
};
51.64MB, 60ms
