【leetcode刷题】T16-乘积最大子序列
这是木又陪伴你的第26天
今天分享leetcode第16篇文章，也是leetcode第152题—乘积最大子序列（Maximum Product Subarray），地址是：https://leetcode.com/problems/maximum-product-subarray/
【英文题目】（学习英语的同时，更能理解题意哟~）
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
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.
【中文题目】
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
【思路】
如果你明白昨天的分享「最大子数组和」：使用变量存储到当前元素为止的子序列的最大和，递推公式为：dp = max(dp+num, num)
那么同理可以使用变量存储到当前元素为止的子序列的最大乘积，得到今天的递推公式：dp = max(dp*num, num)
等等，好像不对吧，要是num<0，这不是有问题吗？
是的，当num>=0，上诉递推公式是没问题的
但是当num<0时，应该在 到前一个元素为止的子序列最小乘积*num 和num中选择最大值
总结来说，tmp_max表示到前一个元素为止的子序列最大乘积； tmp_min表示到前一个元素为止的子序列最小乘积，那么tmp_max = max(tmp_max*num, tmp_min*num, num)，tmp_min = min(tmp_max*num, tmp_min*num, num)
举例来说，对于[-2, 0, -1, -3]
初始化tmp_max = nums[0]，tmp_min = nums[0]，当前最大值res = nums[0]
对于第1个元素，tmp_max = max(tmp_max*num, tmp_min*num, num) = max(-2*0, -2*0, 0) = 0，同理tmp_min = 0，res = max(tmp_max, res) = max(0, -2) = 0
对于第2个元素，tmp_max = max(0*-1, 0*-1, -1) = 0，tmp_min = -1，res = max(0, 0) = 0
对于第3个元素，tmp_max = max(0*-3, -1*-3, -3) = 3，tmp_min = 0，res = max(3, 0) = 3
最终结果为3
【代码】
python版本
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 1:
return None
tmp_max = nums[0]
tmp_min = nums[0]
res = tmp_max
for num in nums[1:]:
# num >= 0，最大值、最小值直接乘以num即可或者直接是num
if num >= 0:
tmp_max = max(num, tmp_max * num)
tmp_min = min(num, tmp_min * num)
# num < 0，最大值为tmp_min*num或者num，最小值为tmp_max(num)或者num
else:
tmp_max, tmp_min = max(num, tmp_min * num), min(num, tmp_max * num)
# 可写为：
# res1, res2 = tmp_max * num, tmp_min * num
# tmp_max = max(res1, res2, num)
# tmp_min = min(res1, res2, num)
if tmp_max > res:
res = tmp_max
return res
C++版本
class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.size() < 1)
return NULL;
int tmp_max = nums[0];
int tmp_min = nums[0];
int res = nums[0];
for(int i=1; i < nums.size(); i++){
// tmp_max * nums[i], tmp_min * nums[i], nums[i]三者中取最大值最小值
int res1 = tmp_max * nums[i];
int res2 = tmp_min * nums[i];
tmp_max = max(max(res1, res2), nums[i]);
tmp_min = min(min(res1, res2), nums[i]);
if(tmp_max > res)
res = tmp_max;
}
return res;
}
};
相关文章：
T15-最大子数组和
给我好看