企业建设电子商务网站的目的,建设人才网站的目的,浙江网站建设工作室,自贡建网站【问题描述】[中等]
给你一个整数数组 nums #xff0c;请你找出数组中乘积最大的连续子数组#xff08;该子数组中至少包含一个数字#xff09;#xff0c;并返回该子数组所对应的乘积。示例 1:输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:输入:…【问题描述】[中等]
给你一个整数数组 nums 请你找出数组中乘积最大的连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。示例 1:输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
【解答思路】
1. 动态规划 时间复杂度O(N) 空间复杂度O(N)
public class Solution {public int maxProduct(int[] nums) {int len nums.length;if (len 0) {return 0;}// dp[i][0]以 nums[i] 结尾的连续子数组的最小值// dp[i][1]以 nums[i] 结尾的连续子数组的最大值int[][] dp new int[len][2];dp[0][0] nums[0];dp[0][1] nums[0];for (int i 1; i len; i) {if (nums[i] 0) {dp[i][0] Math.min(nums[i], nums[i] * dp[i - 1][0]);dp[i][1] Math.max(nums[i], nums[i] * dp[i - 1][1]);} else {dp[i][0] Math.min(nums[i], nums[i] * dp[i - 1][1]);dp[i][1] Math.max(nums[i], nums[i] * dp[i - 1][0]);}}// 只关心最大值需要遍历int res dp[0][1];for (int i 1; i len; i) {res Math.max(res, dp[i][1]);}return res;}
}
2. 动态规划优化 表格复用 时间复杂度O(N) 空间复杂度O(1)
public class Solution {public int maxProduct(int[] nums) {int len nums.length;if (len 0) {return 0;}int preMax nums[0];int preMin nums[0];// 滚动变量int curMax;int curMin;int res nums[0];for (int i 1; i len; i) {if (nums[i] 0) {curMax Math.max(preMax * nums[i], nums[i]);curMin Math.min(preMin * nums[i], nums[i]);} else {curMax Math.max(preMin * nums[i], nums[i]);curMin Math.min(preMax * nums[i], nums[i]);}res Math.max(res, curMax);// 赋值滚动变量preMax curMax;preMin curMin;}return res;}
}
class Solution {public int maxProduct(int[] nums) {int max Integer.MIN_VALUE, imax 1, imin 1; //一个保存最大的一个保存最小的。for(int i0; inums.length; i){if(nums[i] 0){ int tmp imax; imax imin; imin tmp;} //如果数组的数是负数那么会导致最大的变最小的最小的变最大的。因此交换两个的值。imax Math.max(imax*nums[i], nums[i]);imin Math.min(imin*nums[i], nums[i]);max Math.max(max, imax);}return max;}
}【总结】
1.无后效性 无后效性是指如果在某个阶段上过程的状态已知则从此阶段以后过程的发展变化仅与此阶段的状态有关而与过程在此阶段以前的阶段所经历过的状态无关。利用动态规划方法求解多阶段决策过程问题过程的状态必须具备无后效性 「动态规划」通常不关心过程只关心「阶段结果」这个「阶段结果」就是我们设计的「状态」。什么算法关心过程呢「回溯算法」「回溯算法」需要记录过程复杂度通常较高。
而将状态定义得更具体通常来说对于一个问题的解决是满足「无后效性」的。这一点的叙述很理论化不熟悉朋友可以通过多做相关的问题来理解「无后效性」这个概念。
2.做题通常可以不先考虑优化空间
空间通常来说是用户不敏感的并且在绝大多数情况下空间成本低我们写程序通常需要优先考虑时间复杂度最优时间复杂度和空间复杂度通常来说不可能同时最优所以我们经常看到的是优化解法思路都是「空间换时间」这一点几乎贯穿了基础算法领域的绝大多数的算法设计思想限制空间的思路通常来说比较难一般是在优化的过程中才考虑优化空间在一些限制答题时间的场景下例如面试先写出一版正确的代码是更重要的并且不优化空间的代码一般来说可读性和可解释性更强。
3.动态规划总结
动态规划问题通常用于计算多阶段决策问题的最优解。 多阶段是指解决一个问题有多个步骤 最优解是指「最优子结构」。
动态规划有三个概念很重要 重复子问题因为重复计算所以需要「空间换时间」记录子问题的最优解 最优子结构规模较大的问题的最优解由各个子问题的最优解得到 无后效性上面已经解释。
动态规划有两个特别关键的步骤 设计状态
有些题目问啥就设计成什么如果不行只要有利于状态转移很多时候就可以设计成状态根据过往经验还有一部分问题是需要在思考的过程中调整的例如本题。
**推导状态转移方程**通常是由问题本身决定的。
动态规划问题思考的两个方向
自顶向下即「递归 记忆化」入门的时候优先考虑这样做自底向上即「递归」从一个最小的问题开始逐步得到最终规模问题的解。后面问题见得多了优先考虑这样做绝大部分动态规划问题可以「自底向上」通过递推得到。
转载链接https://leetcode-cn.com/problems/maximum-product-subarray/solution/dong-tai-gui-hua-li-jie-wu-hou-xiao-xing-by-liweiw/
