动态规划技术(DP)，能获得更好的时间性能。不过，灵活运用还需要多加训练，多多思考。
1
此题出自LeetCode：152. Maximum Product Subarray，大意求子数组的最大值，举例子1：
1Input: [2,3,-2,4]2Output: 634Explanation: [2,3] has the largest product 6.
例子2：
1Input: [-2,0,-1]2Output: 03Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
这个题目，当然可以用穷举所有子数组的方法，找出最大值，时间复杂度妥妥地为O(n^2)，这显然不是我们想要的。如何用DP降低到O(n)才是我们的目标，这才是算法的魅力所在，接下来，总结DP求解的思维过程。
2
分析一个数组，假定每一个元素都不小于0，如，[2, 3, 0 , 4], ok, 当子数组 [2]，最大连乘为2，当子数组为[2,3]，最大连乘可能的组合：3，2*3，最大子数组为：[2,3]，如果标记dp[i] 表示为以i(含i)为索引的数组的最大值，则 dp[i] 如何 从 dp[i-1] 中推导出来？
dp[i] 取值有以下几种情况：
1) a[i]
2) dp[i-1] * a[i]
则，dp[i] = max( a[i], dp[i-1] * a[i] )
验证以上数组当索引为2时，dp[2] = max(0, 6*0) = 0，dp[3] = max(4, 0 *4) = 4, 因此 max(dp[0],dp[1],dp[2],dp[3]) = dp[1]
如果这道题目
如果元素都为非负，以上递推公式就可解决此题。但是这道题目难就难在元素有负值，比如：[-2, -3, -2, 4]，如果还是按照上述递推公式，dp[0] = -2, dp[1] = 6, dp[2] = -2 , dp[3] = 4，因此最大累乘为：6， 这是错误的。最大累乘应该为：(-3)*(-2)*4 = 24.
问题出在哪里？ dp[0], dp[1] 计算正确，dp[2]错误，因为[-2,-3,-2] 的最大累乘为：(-3)*(-2) = 6.
在哪里摔倒就在哪里爬起来，在计算dp[2]时，按照递推 max(a[2], a[2]*dp[1])计算时，a[2]*dp[1] = -12 ，如果我们再标记一个最小值，dpmin[i]表示为以i为索引的最小值，dpmin[0] = -2, 因为a[1] = -3 <0, 求 dpmin[1] 时先和dp[0]和dpmin[0]交换，因此，dpmin[1] = min(-3, -3*dpmin[0] ) = -3，同样，求dpmin[2]时，dp[1]和dpmin[1]交换，dpmin[2] = min(-2, -2*dp[1] ) = -12, dp[2] = max(-2, -2*dpmin[1]) = 6.
以上关键步骤，涉及到对第 i 个元素为负数时的处理过程，dp[i] 和 dpmin[i] 计算有怎样的依赖关系，当a[i] 为负数时，dp[i-1] * a[i] 变为最小，dpmin[i-1] * a[i] 变为最大，因此交换dp[i-1]和dpmin[i-1]后，dp[i] = max(a[i], dpmin[i-1]*a[i]), dpmin[i] = min(a[i], dp[i-1]*a[i]).
分析完毕
3
本题的代码如下：
求连续子数组的最小值代码稍作修改也出来了。本题还有其他优秀的解吗？欢迎大家分享。
如果是求子数组的非连续最大、小值，该怎么求解大家思考一下吧。
閱讀更多 人工智能channel 的文章
