【問題描述】[中等]

給你一個整數數組 nums ，請你找出數組中乘積最大的連續(xù)子數組（該子數組中至少包含一個數字），并返回該子數組所對應的乘積。示例 1:輸入: [2,3,-2,4] 輸出: 6 解釋: 子數組 [2,3] 有最大乘積 6。 示例 2:輸入: [-2,0,-1] 輸出: 0 解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。

【解答思路】

1. 動態(tài)規(guī)劃

時間復雜度：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] 結尾的連續(xù)子數組的最小值// dp[i][1]：以 nums[i] 結尾的連續(xù)子數組的最大值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. 動態(tài)規(guī)劃優(yōu)化 表格復用

時間復雜度：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 i=0; i<nums.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.無后效性

無后效性是指如果在某個階段上過程的狀態(tài)已知，則從此階段以后過程的發(fā)展變化僅與此階段的狀態(tài)有關，而與過程在此階段以前的階段所經歷過的狀態(tài)無關。利用動態(tài)規(guī)劃方法求解多階段決策過程問題，過程的狀態(tài)必須具備無后效性

「動態(tài)規(guī)劃」通常不關心過程，只關心「階段結果」，這個「階段結果」就是我們設計的「狀態(tài)」。什么算法關心過程呢？「回溯算法」，「回溯算法」需要記錄過程，復雜度通常較高。

而將狀態(tài)定義得更具體，通常來說對于一個問題的解決是滿足「無后效性」的。這一點的敘述很理論化，不熟悉朋友可以通過多做相關的問題來理解「無后效性」這個概念。

2.做題通常可以不先考慮優(yōu)化空間

• 空間通常來說是用戶不敏感的，并且在絕大多數情況下，空間成本低，我們寫程序通常需要優(yōu)先考慮時間復雜度最優(yōu)；
• 時間復雜度和空間復雜度通常來說不可能同時最優(yōu)，所以我們經?？吹降氖莾?yōu)化解法思路都是「空間換時間」，這一點幾乎貫穿了基礎算法領域的絕大多數的算法設計思想；
• 限制空間的思路，通常來說比較難，一般是在優(yōu)化的過程中才考慮優(yōu)化空間，在一些限制答題時間的場景下（例如面試），先寫出一版正確的代碼是更重要的，并且不優(yōu)化空間的代碼一般來說，可讀性和可解釋性更強。

3.動態(tài)規(guī)劃總結

動態(tài)規(guī)劃問題通常用于計算多階段決策問題的最優(yōu)解。
多階段，是指解決一個問題有多個步驟；
最優(yōu)解，是指「最優(yōu)子結構」。

動態(tài)規(guī)劃有三個概念很重要：
重復子問題：因為重復計算，所以需要「空間換時間」，記錄子問題的最優(yōu)解；
最優(yōu)子結構：規(guī)模較大的問題的最優(yōu)解，由各個子問題的最優(yōu)解得到；
無后效性（上面已經解釋）。

動態(tài)規(guī)劃有兩個特別關鍵的步驟：
設計狀態(tài)：

• 有些題目問啥，就設計成什么；
• 如果不行，只要有利于狀態(tài)轉移，很多時候，就可以設計成狀態(tài)；
• 根據過往經驗；
• 還有一部分問題是需要在思考的過程中調整的，例如本題。

**推導狀態(tài)轉移方程：**通常是由問題本身決定的。

動態(tài)規(guī)劃問題思考的兩個方向：

• 自頂向下：即「遞歸 + 記憶化」，入門的時候優(yōu)先考慮這樣做；
• 自底向上：即「遞歸」，從一個最小的問題開始，逐步得到最終規(guī)模問題的解。后面問題見得多了，優(yōu)先考慮這樣做，絕大部分動態(tài)規(guī)劃問題可以「自底向上」通過遞推得到。

轉載鏈接：https://leetcode-cn.com/problems/maximum-product-subarray/solution/dong-tai-gui-hua-li-jie-wu-hou-xiao-xing-by-liweiw/

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第152题][乘积最大子数组][动态规划]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。