給你一個整數數組?
nums?，請你找出數組中乘積最大的非空連續子數組（該子數組中至少包含一個數字），并返回該子數組所對應的乘積。測試用例的答案是一個?32-位?整數。
示例 1:
輸入: nums = [2,3,-2,4] 輸出:6解釋:?子數組 [2,3] 有最大乘積 6。示例 2:
輸入: nums = [-2,0,-1] 輸出: 0 解釋:?結果不能為 2, 因為 [-2,-1] 不是子數組。提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums?的任何子數組的乘積都?保證?是一個?32-位?整數
?要求非空連續子數組對應的最大乘積，由于數組中都是整數，首先應該想到乘積是乘的數越多乘積越大，但是前提是相乘之后為正數。
題目中數組中存在負數，那么會導致最大的值變的最小，最小的值變的最大。
于是我們可以通過遍歷數組，定義一個初始值為1的變量，依次乘以數組的值，每次取最大值，但是只從前往后乘，會出現 -2，2，2，2，2這種情況，導致最大值一直是負數，但是實際上最大值應該是2*2*2*2。因此我們可以再從后往前乘，就能求出上述例子的最大值。下面給出實際代碼：
class Solution {public int maxProduct(int[] nums) {int n = nums.length;int res = nums[0];int x = 1;for(int i = 0;i < n;i++){x *= nums[i];res = Math.max(res,x);if(nums[i] == 0) x = 1;}x = 1;for(int i = n - 1;i >= 0;i--){x *= nums[i];res = Math.max(res,x);if(nums[i] == 0) x = 1;}return res;}
}
?方法二：動態規劃
由上述分析可知，數組中存在負數，那么會導致最大的值變的最小，最小的值變的最大。
因此我們需要維護兩個數組，一個存儲最大值，一個存儲最小值，每次對比當前值和二者乘以當前數，取三者最大值。
即
imax[i] = Math.max(Math.max(imax[i-1] * x,imin[i-1] * x),x);下面給出代碼
class Solution {public int maxProduct(int[] nums) {int n = nums.length;int res = nums[0];int[] imax = new int[n];int[] imin = new int[n];imax[0] = imin[0] = nums[0];for(int i = 1;i < n;i++){int x = nums[i];imax[i] = Math.max(Math.max(imax[i-1] * x,imin[i-1] * x),x);imin[i] = Math.min(Math.min(imin[i-1] * x,imax[i-1] * x),x);res = Math.max(res,imax[i]);}return res;}
}?
?
