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

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

原题

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

示例 1:

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

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

原题url:https://leetcode-cn.com/probl...

解题

暴力求解

看到这道题,第一眼想到的就是暴力求解,从第一个数字开始,一直连续着求到最后。稍微增加了对于 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的解法,看来可以继续优化。

找规律

我们设想一下,如果这个整数数组只有正数,那么最大值就只需要将所有数字相乘即可。

如果包含负数,那么需要分成两种情况:

  1. 负数为偶数个,因为负负得正,所以依旧将所有数字相乘即可。
  2. 负数为奇数个,要么从前往后乘到最后一个负数之前,要么从后往前乘到第一个负数之前。

如果包含 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/

公众号:健程之道

你可能感兴趣的