LeetCode——乘积最大子序列
题目描述
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
一、CPP
1. 动态规划法：
解题思路:本题的难点在于子数组在连乘的时候会遇到以下几种情况：
- 正负号改变：最大值和最小值改变顺序
- 0乘和乘0：导致子数组元素相乘的时候一直为0
- 子数组索引改变
对于第一个难点，可以设置两个数组f[i]，g[i]。其中 f[i] 表示子数组 [0, i] 范围内并且一定包含 nums[i]数字的最大子数组乘积，g[i] 表示子数组 [0, i] 范围内并且一定包含 nums[i] 数字的最小子数组乘积，初始化时 f[0] 和 g[0] 都初始化为 nums[0]，其余都初始化为0。设置这两个数组就是为了即使nums[i+1]为负，也能得到最大值。
对于第二和第三个难点，可以对当前最大值(从f[i]或g[i]得到) 与nums[i]进行比较，当之前遍历的所有子数组没有nums[i]大时，使用nums[i]更新子数组开始的索引。
即最大值和最小值只会在这三个数字之间产生，即 f[i-1]*nums[i]，g[i-1]*nums[i]，和 nums[i]。所以用三者中的最大值来更新 f[i]，用最小值来更新 g[i]，然后用 f[i] 来更新结果 res 即可，由于最终的结果不一定会包括 nums[n-1] 这个数字，所以 f[n-1] 不一定是最终解，不断更新的结果 res 才是。
时间复杂度:O(n)。
空间复杂度:O(1)。
class Solution {
public:
int maxProduct(vector<int>& nums) {
vector<int> f(n, 0), g(n, 0);
int res = nums[0], n = nums.size();
f[0] = nums[0];
g[0] = nums[0];
for (int i = 1; i < n; ++i) {
f[i] = max(max(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]);
g[i] = min(min(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]);
res = max(res, f[i]);
}
return res;
}
};
本解法参考博客。
2. 方法一改进版：
解题思路:在方法一的基础上进行改进，不是无脑的比较三个数的大小，而是先判断一下nums[i]是正还是负。如果是负就交换最大值和最小值。然后mx * nums[i]再与nums[i]进行比较。最后更新res。
时间复杂度:O(n)。
空间复杂度:O(1)。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0], mx = res, mn = res;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] > 0) {
mx = max(mx * nums[i], nums[i]);
mn = min(mn * nums[i], nums[i]);
} else {
int tmp = mx;
mx = max(mn * nums[i], nums[i]);
mn = min(tmp * nums[i], nums[i]);
}
res = max(res, mx);
}
return res;
}
};
3. 两次遍历法：
解题思路:解法遍历了两次，一次是正向遍历，一次是反向遍历，相当于正向建立一个累加积数组，每次用出现的最大值更新结果 res，然后再反响建立一个累加积数组，再用出现的最大值更新结果 res，注意当遇到0的时候，prod 要重置为1。至于为啥正反两次遍历就可以得到正确的结果了呢？主要还是由于负数个数的关系，因为负数可能会把最大值和最小值翻转，那么当有奇数个负数时，如果只是正向遍历的话，可能会出错，比如 [-1, -2, -3]，累加积会得到 -1，2，-6，看起来最大值只能为2，其实不对，而如果我们再反向来一遍，累加积为 -3，6，-6，就可以得到6了。所以当负数个数为奇数时，首次出现和末尾出现的负数就很重要，有可能会是最大积的组成数字，所以遍历两次就不会漏掉组成最大值的机会。
时间复杂度:O(n)。
空间复杂度:O(1)。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0], prod = 1, n = nums.size();
for (int i = 0; i < n; ++i) {
res = max(res, prod *= nums[i]);
if (nums[i] == 0) prod = 1;
}
prod = 1;
for (int i = n - 1; i >= 0; --i) {
res = max(res, prod *= nums[i]);
if (nums[i] == 0) prod = 1;
}
return res;
}
};
注意：其实这个题可以使用一次遍历就能解决，更好的解释方法如下：
把题目简单化，理清思路后会发现其实会出现数组序列三种情况。
1.数组中全为正数或偶数个负数
做法：全部元素从头到尾相乘即可。
2.数组中有奇数个负数（两种情况）
做法：最后一个负数的左边的乘积大。
做法：最后一个负数的右边的乘积大。
数组中有0
做法：把0全部隔开
方法三完全按照以上思路解题。方法二的做法是通过累积数与nums[i]的比较，来解决以上三种情况。
参考自leetcode评论。
4. 暴力法：
解题思路:由于题目要求必须是连续的子串，所以暴力解法就是遍历每一个元素，计算其右边所有可能子串的乘积，并用result记录每个元素遍历的乘积最大值。关键一步是在给Multiply赋值之后，在for循环之前判断一下是否大于result，因为可能出现[-1,-1,5,-2,0]，这种情况下，如果for循环之前不进行判断，那么5和后面的数相乘不会大于之前的最大数result=2，所以5这个最大数就错过啦。即先判断是防止某个数比他和所有右边数的乘积还要大的情况。
时间复杂度:O(n2)。
空间复杂度:O(1)。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int result = nums[0];
for(int i = 0; i<n; ++i){
int Multiply = nums[i];
//关键一步
if(Multiply>result){
result = Multiply;
}
for(int j=i+1; j<n; ++j){
Multiply *= nums[j];
if(Multiply>result){
result = Multiply;
}
}
}
return result;
}
};
二、Java（方法一改进版）
class Solution {
public int maxProduct(int[] nums) {
int res = nums[0];
int mx = res;
int mn = res;
for(int i = 1; i<nums.length; i++){
if(nums[i] >= 0){
mx = Math.max(mx * nums[i],nums[i]);
mn = Math.min(mn * nums[i],nums[i]);
}
else{
int tmp = mx;
mx = Math.max(mn * nums[i],nums[i]);
mn = Math.min(tmp * nums[i],nums[i]);
}
res = Math.max(res,mx);
}
return res;
}
}
三、Python（方法一改进版）
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = mx = mn = nums[0]
for i in range(1,len(nums)):
if nums[i] >= 0:
mx = max(mx * nums[i], nums[i])
mn = min(mn * nums[i], nums[i])
else:
tmp = mx
mx = max(mn * nums[i], nums[i])
mn = min(tmp * nums[i], nums[i])
res = max(res, mx)
return res
四、各语言及算法时间复杂度
