力扣152——乘积最大子序列
这道题主要就是利用动态规划进行解答，如果要进行优化，就需要找规律了。
原题
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
原题url：https://leetcode-cn.com/problems/maximum-product-subarray/
解题
暴力求解
看到这道题，第一眼想到的就是暴力求解，从第一个数字开始，一直连续着求到最后。稍微增加了对于 0 的判断，因为 0 乘以任何数都等于 0，所以只要碰到 0，当前的这次求解就可以停止。让我们看看代码：
class Solution {
int max = Integer.MIN_VALUE;
public int maxProduct(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
if (max < 0) {
max = 0;
}
continue;
}
dfs(nums, i + 1, nums[i]);
}
return max;
}
public void dfs(int[] nums, int index, int total) {
// 当前乘积是否最大
if (total > max) {
max = total;
}
// 有没有越界
if (index >= nums.length) {
return;
}
// 当前数字是否是0，是0的话就没有必要继续下去，因为乘积永远为0
if (nums[index] == 0) {
return;
}
dfs(nums, index + 1, total * nums[index]);
}
}
提交之后，报超出时间限制。看来暴力求解果然不可取，让我们再想想。
动态规划
既然不能暴力求解，那我们能不能利用上之前求解的结果呢？没错，这就是动态规划了。
原本想着是逐个求出当前下标下的最大值，但因为是乘积，考虑到负负得正的情况，只记录最大值可能还不够，需要最大值和最小值一起记录。
但根据之前优化的经验，并不需要申请额外的数组存储最大值和最小值，只需要用常数量的空间存储之前的结果，因为题目要求的是连续，只需要记录上一个序号的结果就够了。
接下来看看代码：
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
// 包含上一个位置的数，得出来的最大值和最小值
int dpMax = nums[0], dpMin = nums[0];
// 最终结果的最大值
int max = nums[0];
// 遍历求解
for (int i = 1; i < n; i++) {
// 更新 dpMin 的时候需要 dpMax 之前的信息，所以先保存起来
int preMax = dpMax;
// 求出 (dpMin * nums[i])、(dpMax * nums[i])、nums[i] 这三个数的最大值和最小值
dpMax = Math.max(dpMin * nums[i], Math.max(dpMax * nums[i], nums[i]));
dpMin = Math.min(dpMin * nums[i], Math.min(preMax * nums[i], nums[i]));
// 更新最终的最大值
max = Math.max(max, dpMax);
}
return max;
}
}
提交OK，执行用时：2 ms，内存消耗：38.1 MB。但似乎还有稳定耗时只要1 ms的解法，看来可以继续优化。
找规律
我们设想一下，如果这个整数数组只有正数，那么最大值就只需要将所有数字相乘即可。
如果包含负数，那么需要分成两种情况：
- 负数为偶数个，因为负负得正，所以依旧将所有数字相乘即可。
- 负数为奇数个，要么从前往后乘到最后一个负数之前，要么从后往前乘到第一个负数之前。
如果包含 0，那么依旧只需要从前往后和从后往前各乘一遍，只是在遇到 0 的时候，将之前相乘所得到的结果置为 1 即可，这样就可以达到单独计算中间数字连续相乘的效果。
根据上面的规律，其实就是从后往前、从前往后，各乘一遍，找出最大结果即可。接下来看看代码：
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) {
return 0;
}
// 记录中间相乘的结果
int max = 1;
// 记录最终的结果
int res = nums[0];
// 从前往后乘一遍
for (int i = 0; i < nums.length; i++) {
max *= nums[i];
res = Math.max(res, max);
// 如果遇到 0，则将中间记录的结果置为 1
if (max == 0) {
max = 1;
}
}
max = 1;
// 从后往前乘一遍
for (int i = nums.length - 1; i >= 0; i--) {
max *= nums[i];
res = Math.max(res, max);
// 如果遇到 0，则将中间记录的结果置为 1
if (max == 0) {
max = 1;
}
}
return res;
}
}
提交OK，执行用时：1 ms，内存消耗：36.3 MB。这个方法真的是又快又省空间，只是需要我们耐心寻找其中的规律。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。一般来说利用动态规划就够了，如果想继续优化，就需要寻找其中的规律了。
有兴趣的话可以访问我的博客或者关注我的公众号，说不定会有意外的惊喜。
https://death00.github.io/
公众号：健程之道