大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到有深信服内部员工爆料公司取消了月初周六上午加班的调休，据说往年月初周六上午加的班会放到过年统一调休，这样全年就会产生6天调休假，但是从今年起过年只给4天调休，并且公司内部发文称年底的假期并非调休而是公司福利。拒爆料平时周末加班也不再给加班费，只能换成调休，调休过期就作废。而且很多员工加班也不让走正式的审批流程，各自在自己的小本本上记下自己加了几天班，调休的时候也不用提审批流程直接抵扣。
新的制度引发了深信服内部激烈的讨论，有些人认为如果年底的假是公司福利并非调休，那月初周六加的班就是被白嫖了。据说内部论坛因为这件事被取消了匿名功能，不知道是不是真的，有没有深信服的同学，可以分享一下。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道高频面试题「乘积最大子数组」。
题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
举个例子：
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
思路解析
这是一道经典的动态规划题目，动态规划的关键就是推导状态转移公式，接下来带你一步步来推导。
定义cur_max[i]表示以nums中第i个元素结尾子数组乘积最大的值，其中0 <= i < nums.size。在推导cur_max[i]的过程中会枚举以nums中任意元素结尾，乘积最大的子数组。最终我们从cur_max[i]中选择最大的一个即是最终要返回的结果。
那么cur_max[i]要怎么算呢？
数组元素全部都是大于 0的场景：
在这种场景下，因为元素都是正数，不难看出cur_max[i] = cur_max[i-1] * nums[i]。
数组元素中含 0的场景：
这个时候，cur_max[2] = 0，nums[3] = 3，如果继续套用上面的公式算出cur_max[3] = cur_max[2] * nums[3] = 0，显然这是不对的，正确的cur_max[3] = nums[3] = 3。我们需要修改下上面的公式，cur_max[i] = max{cur_max[i-1] * nums[i], nums[i]}。
数组元素包含负数的场景：
负数比较特殊，cur_max[2] = -1，但cur_max[3] != max{cur_max[2] * nums[3], nums[3]}。这是因为负数的存在可能会导致最大值乘以负数变最小值，最小值乘以负数变最大值。针对这种情况我们增加一个数组cur_min[i]来表示以nums中第i个元素结尾子数组乘积最小的值，这个时候最终获得的状态转移公式如下。
cur_max[i] = max{cur_max[i-1] * nums[i], cur_min[i-1] * nums[i], nums[i]}。
cur_min[i] = min{cur_max[i-1] * nums[i], cur_min[i-1] * nums[i], nums[i]}。
实现优化
上面的状态转移公式如果用代码来实现需要利用两个跟nums长度一致的数组cur_min和cur_max。因为题目要求找到子数组最大的乘积，我们不需要把每个子数组的状态都保存下来，只保存上一个状态就可以。利用一个整型变量max_res来保存全局的最大乘积。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
int maxProduct(vector<int>& nums) {
int nums_len = nums.size();
int max_res = INT_MIN;
long long cur_max = 1, cur_min = 1;
for (int i = 0; i < nums_len; ++i) {
//提前保存一下cur_max和cur_min前一个状态，避免更新cur_min的时候用了最新状态的cur_max
long long temp_max = cur_max, temp_min = cur_min;
//状态转移公式
cur_max = max(max(temp_max * nums[i], temp_min * nums[i]), (long long)nums[i]);
cur_min = min(min(temp_max * nums[i], temp_min * nums[i]), (long long)nums[i]);
if (cur_min < INT_MIN) {
cur_min = INT_MIN;
}
//更新全局最大值
max_res = max(max_res, (int)cur_max);
}
return max_res;
}
};
python代码
class Solution:
def maxProduct(self, nums: List[int]) -> int:
nums_len = len(nums)
max_res = float('-inf')
cur_max = 1
cur_min = 1
for i in range(nums_len):
# 提前保存一下cur_max和cur_min前一个状态，避免更新cur_min的时候用了最新状态的cur_max
temp_max = cur_max
temp_min = cur_min
# 状态转移公式
cur_max = max(max(temp_max * nums[i], temp_min * nums[i]), nums[i])
cur_min = min(min(temp_max * nums[i], temp_min * nums[i]), nums[i])
# 更新全局最大值
max_res = max(max_res, cur_max)
return max_res
复杂度分析
时间复杂度： 整个过程只需要遍历一遍数组nums，故时间复杂度为O(n)，其中n为nums的长度。
空间复杂度： 整个过程只用到了整型变量，故空间复杂度为O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
