Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
<pre class="highlighter-hljs" highlighted="true" has-selection="true" style="margin: 10px auto; padding: 0px; transition-duration: 0.2s; transition-property: background, font-size, border-color, border-radius, border-width, padding, margin, color; overflow: auto; color: rgb(73, 73, 73); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
</pre>
Example 2:
<pre style="margin: 10px auto; padding: 0px; transition-duration: 0.2s; transition-property: background, font-size, border-color, border-radius, border-width, padding, margin, color; overflow: auto; color: rgb(73, 73, 73); font-size: 14px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.</pre>
思路：
一開始的暴力解法饱岸，找出所有的子數(shù)組，算出乘積，然后找出比較大的一個(gè)惫撰。但是復(fù)雜度是n2；換思路，dp來做，要用兩個(gè)dp數(shù)組萨驶。其中f[i]表示[0,i]范圍內(nèi)并且包含nums[i]的最大子數(shù)組乘積。g[i]標(biāo)識(shí)[0,i]范圍內(nèi)并且包含nums[i]的最小子數(shù)組乘積艇肴。初始化時(shí)f[0]和g[0]都是nums[0];name從數(shù)組的第二個(gè)數(shù)字開始遍歷腔呜，此時(shí)數(shù)組的最大值和最小值置灰在這三個(gè)數(shù)字之間產(chǎn)生，即f[i-1]nums[i];nums[i];g[i-1]nums[i]再悼。所以用這三者中的最大值來更新f[i],用最小值來更新g[i],然后用f[i]來更新res即可核畴。
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
var max = nums[0];
var min = nums[0];
var res = nums[0];
for(var i = 1; i< nums.length; i++) {
var mx = max;
var nx = min;
max = Math.max(mx*nums[i], nums[i], nx*nums[i]);
min = Math.min(mx*nums[i], nums[i], nx*nums[i]);
res = Math.max(max, res);
}
return res;
};
