152 Maximum Product Subarray 乘積最大子數(shù)組
Description:
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example:
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
題目描述:
給你一個整數(shù)數(shù)組 nums 浊闪，請你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個數(shù)字）彤灶，并返回該子數(shù)組所對應(yīng)的乘積。
示例 :
示例 1:
輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6。
示例 2:
輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因為 [-2,-1] 不是子數(shù)組。
思路:
動態(tài)規(guī)劃
dp[i]表示以 nums[i]結(jié)尾的子數(shù)組最大乘積
轉(zhuǎn)移方程 dp[i] = max(dp[i - 1] * nums[i], nums[i]), 這里實際上用一個變量就可以記錄最大值
考慮到 nums[i]如果為負(fù)數(shù), 那么乘積之后到最大值和最小值會交換, 需要同時記錄最大值和最小值
時間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
int maxProduct(vector<int>& nums)
{
int result = nums[0], a = 1, b = 1;
for (auto num : nums)
{
if (num < 0) swap(a, b);
a = max(a * num, num);
b = min(b * num, num);
result = max(a, result);
}
return result;
}
};
Java:
class Solution {
public int maxProduct(int[] nums) {
int result = nums[0], max = 1, min = 1;
for (int num : nums) {
if (num < 0) {
max ^= min;
min ^= max;
max ^= min;
}
max = Math.max(max * num, num);
min = Math.min(min * num, num);
result = Math.max(max, result);
}
return result;
}
}
Python:
class Solution:
def maxProduct(self, nums: List[int]) -> int:
return max(functools.reduce(lambda x, y: [max(x[0] * y, x[1] * y, y), min(x[1] * y, x[0] * y, y), max(x)], nums[1:], [nums[0], nums[0], nums[0]]))
