这是木又陪伴你的第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;
}
};
相关文章:
给我好看