動態規劃技術(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 的文章
