【leetcode】152.乘积最⼤⼦数组（动态规划详细解析，java多种⽅法实现）难度中等715
给你⼀个整数数组 nums ，请你出数组中乘积最⼤的连续⼦数组（该⼦数组中⾄少包含⼀个数字），并返回该⼦数组所对应的乘积。
⽰例 1:
输⼊: [2,3,-2,4]
输出: 6
解释: ⼦数组 [2,3] 有最⼤乘积 6。
⽰例 2:
输⼊: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是⼦数组。
分析
思路
这个问题很像「⼒扣」第 53 题：，只不过当前这个问题求的是乘积的最⼤值；
「连续」这个概念很重要，可以参考第 53 题的状态设计，将状态设计为：以 nums[i]结尾的连续⼦数组的最⼤值；
类似状态设计的问题还有「⼒扣」第 300 题：，「⼦数组」、「⼦序列」问题的状态设计的特点是：以 nums[i] 结尾，这是⼀个经验，可以简化讨论。
提⽰：以 nums[i] 结尾这件事情很重要，贯穿整个解题过程始终，请⼤家留意。
分析与第 53 题的差异
求乘积的最⼤值，⽰例中负数的出现，告诉我们这题和 53 题不⼀样了，⼀个正数乘以负数就变成负数，即：最⼤值乘以负数就变成了最⼩值；
因此：最⼤值和最⼩值是相互转换的，这⼀点提⽰我们可以把这种转换关系设计到「状态转移⽅程」⾥去；
如何解决这个问题呢？这⾥常见的技巧是在「状态设计」的时候，在原始的状态设计后⾯多加⼀个维度，减少分类讨论，降低解决问题的难度。
这⾥是百度百科的词条的解释：
⽆后效性是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，⽽与过程在此阶段以前的阶段所经历过的状态⽆关。利⽤动态规划⽅法求解多阶段决策过程问题，过程的状态必须具备⽆后效性。
再翻译⼀下就是：「动态规划」通常不关⼼过程，只关⼼「阶段结果」，这个「阶段结果」就是我们设计的「状态」。什么算法关⼼过程呢？「回溯算法」，「回溯算法」需要记录过程，复杂度通常较⾼。
⽽将状态定义得更具体，通常来说对于⼀个问题的解决是满⾜「⽆后效性」的。这⼀点的叙述很理论化，不熟悉朋友可以通过多做相关的问题来理解「⽆后效性」这个概念。
第 1 步：状态设计（特别重要）
dp[i][j]
：以nums[i]结尾的连续⼦数组的最值，计算最⼤值还是最⼩值由j 来表⽰，j 就两个值；
当 j = 0 的时候，表⽰计算的是最⼩值；
当 j = 1 的时候，表⽰计算的是最⼤值。
这样⼀来，状态转移⽅程就容易写出。
第 2 步：推导状态转移⽅程（特别重要）
由于状态的设计 nums[i] 必须被选取（请⼤家体会这⼀点，这⼀点恰恰好也是使得⼦数组、⼦序列问题更加简单的原因：当情况复杂、分类讨论⽐较多的时候，需要固定⼀些量，以简化计算）；
nums[i] 的正负和之前的状态值（正负）就产⽣了联系，由此关系写出状态转移⽅程：
当 nums[i] > 0 时，由于是乘积关系：
最⼤值乘以正数依然是最⼤值；
最⼩值乘以同⼀个正数依然是最⼩值；
当nums[i] < 0 时，依然是由于乘积关系：
最⼤值乘以负数变成了最⼩值；
最⼩值乘以同⼀个负数变成最⼤值；
当 nums[i] = 0 的时候，由于 nums[i] 必须被选取，最⼤值和最⼩值都变成 00 ，合并到上⾯任意⼀种情况均成⽴。
但是，还要注意⼀点，之前状态值的正负也要考虑：例如，在考虑最⼤值的时候，当 nums[i] > 0 是，如果 dp[i - 1][1] < 0 （之前的状态最⼤值） ，此时 nums[i] 可以另起炉灶（这⾥依然是第 53 题的思想），此时 dp[i][1] = nums[i] ，合起来写就是：
dp[i][1]=max(nums[i], nums[i]* dp[i -1][1])if nums[i]>=0
其它三种情况可以类似写出，状态转移⽅程如下：
dp[i][0]=min(nums[i], nums[i]* dp[i -1][0])if nums[i]>=0
dp[i][1]=max(nums[i], nums[i]* dp[i -1][1])if nums[i]>=0
dp[i][0]=min(nums[i], nums[i]* dp[i -1][1])if nums[i]<0
dp[i][1]=max(nums[i], nums[i]* dp[i -1][0])if nums[i]<0
第 3 步：考虑初始化
由于 nums[i] 必须被选取，那么 dp[i][0] = nums[0]，dp[i][1] = nums[0]。
第 4 步：考虑输出
题⽬问连续⼦数组的乘积最⼤值，这些值需要遍历 dp[i][1] 获得。
参考代码 1：
Java
return0;
}
// 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;
}
}
复杂度分析：
时间复杂度：O(N)，这⾥ N 是数组的长度，遍历 2 次数组；
空间复杂度：O(N)，状态数组的长度为 2N。
问题做到这个地⽅，其实就可以了。下⾯介绍⼀些⾮必要但进阶的知识。
第 5 步：考虑表格复⽤
动态规划问题，基于「⾃底向上」、「空间换时间」的思想，通常是「填表格」，本题也不例外；
由于通常只关⼼最后⼀个状态值，或者在状态转移的时候，当前值只参考了上⼀⾏的值，因此在填表的过程中，表格可以复⽤，常⽤的技巧有：
1、滚动数组（当前⾏只参考了上⼀⾏的时候，可以只⽤ 2 ⾏表格完成全部的计算）；
2、滚动变量（斐波拉契数列问题）。
掌握⾮常重要的「表格复⽤」技巧，来⾃「0-1 背包问题」（弄清楚为什么要倒序填表）和「完全背包问题」（弄清楚为什么可以正向填表）；
「表格复⽤」的合理性，只由「状态转移⽅程」决定，即当前状态值只参考了哪些部分的值。
参考代码 2：
Java
return0;
}
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;
}
java技术介绍百度百科}
复杂度分析：
时间复杂度：O(N)O(N)，这⾥ N N 是数组的长度，最值也在⼀次遍历的过程中计算了出来；
空间复杂度：O(1)O(1)，只使⽤了常数变量。
这⾥说⼀点题外话：除了基础的「0-1」背包问题和「完全背包」问题，需要掌握「表格复⽤」的技巧以外。在绝⼤多数情况下，在「⼒扣」上做的「动态规划」问题都可以不考虑「表格复⽤」。
做题通常可以不先考虑优化空间（个⼈观点，仅供参考），理由如下：
空间通常来说是⽤户不敏感的，并且在绝⼤多数情况下，空间成本低，我们写程序通常需要优先考虑时间复杂度最优；
时间复杂度和空间复杂度通常来说不可能同时最优，所以我们经常看到的是优化解法思路都是「空间换时间」，这⼀点⼏乎贯穿了基础算法领域的绝⼤多数的算法设计思想；
限制空间的思路，通常来说⽐较难，⼀般是在优化的过程中才考虑优化空间，在⼀些限制答题时间的场景下（例如⾯试），先写出⼀版正确的代码是更重要的，并且不优化空间的代码⼀般来说，可读性和可解释性更强。
以上个⼈建议，仅供参考。
总结
动态规划问题通常⽤于计算多阶段决策问题的最优解。
多阶段，是指解决⼀个问题有多个步骤；
最优解，是指「最优⼦结构」。
动态规划有三个概念很重要：
重复⼦问题：因为重复计算，所以需要「空间换时间」，记录⼦问题的最优解；
最优⼦结构：规模较⼤的问题的最优解，由各个⼦问题的最优解得到；
⽆后效性（上⾯已经解释）。
动态规划有两个特别关键的步骤：
设计状态：
有些题⽬问啥，就设计成什么；
如果不⾏，只要有利于状态转移，很多时候，就可以设计成状态；
根据过往经验；
还有⼀部分问题是需要在思考的过程中调整的，例如本题。
推导状态转移⽅程：通常是由问题本⾝决定的。
动态规划问题思考的两个⽅向：
⾃顶向下：即「递归 + 记忆化」，⼊门的时候优先考虑这样做；
⾃底向上：即「递推」，从⼀个最⼩的问题开始，逐步得到最终规模问题的解。后⾯问题见得多了，优先考虑这样做，绝⼤部分动态规划问题可以「⾃底向上」通过递推得到。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。