力扣152——乘积最大子序列

这道题主要就是利用动态规划进行解答，如果要进行优化，就需要找规律了。

原题

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

1
2
3

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3

输入: [-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;
    }
}