题目链接 : https://leetcode-cn.com/problems/maximum-product-subarray/
题目描述:
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例:
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。思路:
大家做这道题之前, 先做一下53. 最大子序和 | 题解链接
思路一: 类似滑动窗口的感觉
product(i, j) = product(0, j) / product(0, i) 从数组i到j 的累乘等于 从数组开头到j的累乘除以从数组开头到i 的累乘(这里先忽略0的情况), 要考虑三种情况
累乘的乘积等于0,就要重新开始
累乘的乘积小于0, 要找到前面最大的负数, 这样才能保住从i到j最大
累乘的乘积大于0, 要找到前面最小的正数, 同理!
代码如下:
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums: return
# 目前的累乘
cur_pro = 1
# 前面最小的正数
min_pos = 1
# 前面最大的负数
max_neg = float("-inf")
# 结果
res = float("-inf")
for num in nums:
cur_pro *= num
# 考虑三种情况
# 大于0
if cur_pro > 0:
res = max(res, cur_pro // min_pos)
min_pos = min(min_pos, cur_pro)
# 小于0
elif cur_pro < 0:
if max_neg != float("-inf"):
res = max(res, cur_pro // max_neg)
else:
res = max(res, num)
max_neg = max(max_neg, cur_pro)
# 等于0
else:
cur_pro = 1
min_pos = 1
max_neg = float("-inf")
res = max(res, num)
return res 思路二, 动态规划1
我们只要记录前i的最小值, 和最大值, 那么 dp[i] = max(nums[i] * pre_max, nums[i] * pre_min, nums[i]), 这里0 不需要单独考虑, 因为当相乘不管最大值和最小值,都会置0
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums: return
res = nums[0]
pre_max = nums[0]
pre_min = nums[0]
for num in nums[1:]:
cur_max = max(pre_max * num, pre_min * num, num)
cur_min = min(pre_max * num, pre_min * num, num)
res = max(res, cur_max)
pre_max = cur_max
pre_min = cur_min
return resjava
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int res = nums[0];
int pre_max = nums[0];
int pre_min = nums[0];
for (int i = 1; i < nums.length; i++) {
int cur_max = Math.max(Math.max(pre_max * nums[i], pre_min * nums[i]), nums[i]);
int cur_min = Math.min(Math.min(pre_max * nums[i], pre_min * nums[i]), nums[i]);
res = Math.max(res, cur_max);
pre_max = cur_max;
pre_min = cur_min;
}
return res;
}
}思路三: 根据符号的个数2
当负数个数为偶数时候, 全部相乘一定最大
当负数个数为奇数时候, 它的左右两边的负数个数一定为偶数, 只需求两边最大值
当有0情况,重置就可以了
class Solution:
def maxProduct(self, nums: List[int]) -> int:
reverse_nums = nums[::-1]
for i in range(1, len(nums)):
nums[i] *= nums[i - 1] or 1
reverse_nums[i] *= reverse_nums[i - 1] or 1
return max(nums + reverse_nums)