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

栏目: IT技术 · 发布时间: 4年前

内容简介:这道题主要就是利用动态规划进行解答,如果要进行优化,就需要找规律了。给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。示例 1:

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

原题

给定一个整数数组 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 的解法,看来可以继续优化。

找规律

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

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

  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/

公众号:健程之道

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

点击此处留言


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

轻量级Django

轻量级Django

茱莉亚·埃尔曼 (Julia Elman)、马克·拉温 (Mark Lavin) / 侯荣涛、吴磊 / 中国电力出版社; 第1版 / 2016-11-1 / 35.6

自Django 创建以来,各种各样的开源社区已经构建了很多Web 框架,比如JavaScript 社区创建的Angular.js 、Ember.js 和Backbone.js 之类面向前端的Web 框架,它们是现代Web 开发中的先驱。Django 从哪里入手来适应这些框架呢?我们如何将客户端MVC 框架整合成为当前的Django 基础架构? 本书讲述如何利用Django 强大的“自支持”功......一起来看看 《轻量级Django》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具