[LeetCode] 152. Maximum Product

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>
思路：
一开始的暴力解法，找出所有的子数组，算出乘积，然后找出比较大的一个。但是复杂度是n2；换思路，dp来做，要用两个dp数组。其中f[i]表示[0,i]范围内并且包含nums[i]的最大子数组乘积。g[i]标识[0,i]范围内并且包含nums[i]的最小子数组乘积。初始化时f[0]和g[0]都是nums[0];name从数组的第二个数字开始遍历，此时数组的最大值和最小值置灰在这三个数字之间产生，即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;
};