「图解大厂面试高频算法题」动态规划-乘积最大子数组
2021/12/11 22:46:42
本文主要是介绍「图解大厂面试高频算法题」动态规划-乘积最大子数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
「图解大厂面试高频算法题」动态规划-乘积最大子数组
原题链接: https://leetcode-cn.com/problems/maximum-product-subarray/
题目介绍
PS: 动态规划题型中最最经典的入门题目。
示例1
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例2
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
题目解答
方法一:一维动态规划
思路和算法
大家可以先思考一下子数组构成的要素,有这么一个关键点,那就是这个数组肯定有一个起始元素和一个末尾元素,如果我们算出了以nums[i-1]元素为末尾的子数组乘积的最大值,那以nums[i]元素为末尾的子数组乘积的最大值是不是就是max(nums[i-1]元素为末尾的子数组乘积的最大值 * nums[i], nums[i])?大家可以仔细思考一下。
其实离正确答案很接近了,就差了一点点,因为没有考虑到有nums数组里有负数的情况。如果nums[i]元素为负数,如果可以找到一个以nums[i-1]元素为末尾的子数组乘积的最小值(最好也是负数),与nums[i]相乘是不是就有可能得到一个更大的数?确实如此,那我们尝试去写一下状态转移方程。
构建两个dp数组dpMax和dpMin。
- dpMax[i]表示以nums[i]元素结尾的子数组的乘机,且乘机是最大的。
- dpMin[i]表示以nums[i]元素结尾的子数组的乘机,且乘机是最小的。
这样我们就可以得出状态转移方程
- dpMax[i] = max(nums[i], dpMax[i-1] * nums[i], dpMin[i-1] * nums[i]);
- dpMin[i] = min(nums[i], dpMax[i-1] * nums[i], dpMin[i-1] * nums[i]);
图解算法
第一次迭代
第二次迭代
第三次迭代
这次迭代完后,达到了终止状态,最终的结果为48
代码实现
class Solution { public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int[] dpMax = new int[nums.length]; int[] dpMin = new int[nums.length]; dpMax[0] = nums[0]; dpMin[0] = nums[0]; int result = nums[0]; for (int i = 1; i < nums.length; i++) { dpMax[i] = Math.max(nums[i], Math.max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i])); dpMin[i] = Math.min(nums[i], Math.min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i])); result = Math.max(result, dpMax[i]); } return result; } }
复杂度分析
- 时间复杂度:程序一次循环遍历了 nums,故渐进时间复杂度为 O(n)。
- 空间复杂度:new了两个dp数组,故空间复杂度为 O(n)。
方法二:迭代(动态规划优化版)
思路和算法
在一维动态规划中我们需要new两个dp数组,导致了额外的空间占用。根据滚动数组思想,使用两个临时遍历就可以把dp数组优化掉。
代码实现
class Solution { public int maxProduct(int[] nums) { int result = nums[0]; int max = nums[0]; int min = nums[0]; for (int i = 1; i < nums.length; i++) { int maxt = Math.max(nums[i]*min, Math.max(nums[i]*max, nums[i])); int mint = Math.min(nums[i]*min, Math.min(nums[i]*max, nums[i])); result = Math.max(result, maxt); max = maxt; min = mint; } return result; } }
复杂度分析
- 时间复杂度:程序一次循环遍历了 nums,故渐进时间复杂度为 O(n)
- 空间复杂度:优化后只使用常数个临时变量作为辅助空间,与 n 无关,故渐进空间复杂度为 O(1)
这篇关于「图解大厂面试高频算法题」动态规划-乘积最大子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南