内容简介:这道题主要就是利用动态规划进行解答,如果要进行优化,就需要找规律了。给定一个整数数组 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
的解法,看来可以继续优化。
找规律
我们设想一下,如果这个整数数组只有正数,那么最大值就只需要将所有数字相乘即可。
如果包含负数,那么需要分成两种情况:
-
负数为偶数个,因为负负得正,所以依旧将所有数字相乘即可。
-
负数为奇数个,要么从前往后乘到最后一个负数之前,要么从后往前乘到第一个负数之前。
如果包含 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/
公众号:健程之道
点击此处留言
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode日记_01,乘积最大子序列
- 蓝桥杯 ADV-189 算法提高 连接乘积
- 算法 - 找出数组中子集乘积的最大值
- 蓝桥杯 ADV-13 算法提高 最小乘积(提高型)
- LeetCode每日一题: 三个数的最大乘积(No.628)
- Java 序列化反序列化对比
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。