动态规划4：乘积最大子序列

给定一个数组，找到其连续子序列的最大乘积。

例如：

2, 3, -2, 4 ==> 6
-2, 0, -1 ==> 0
2, 3, -10, 5, -1 ==> 300

---

分析：

尝试定义状态: f(n)为以arr[n]结尾的子序列的最大乘积，则 max[f(0), f(1), ...fn(n)]即为所求
状态转移方程：fn(n) = min(f(n-1) * arr[n], arr[n])
额，等等，arr[n]是可能为负数的，最大值乘以负数就会成为最小值，所以此时还需要前面的最大负值相乘才能得到当前最大乘积 ==> 目前定义的f(n)不满足需求。

我们需要同时记录以n结尾的最大值和最小值。

一位数组定义状态不满足时，我们可以使用二维数组。但针对此问题定义两个状态也能解决问题，并且对js更友好，毕竟js不像其他语言定义二维数组那么方便

定义状态：

max(n)为以arr[n]结尾的子序列的最大值
minus_max(n) 为以arr[n]结尾的子序列的最小值

状态转移方程：

max(n+1) = arr[n+1] > 0 ?
  Math.max(max(n) * arr[n+1], arr[n+1]) :
  Math.max(min(n) ( arr[n+1], arr[n+1])

min(n+1)同理，但这样太过麻烦了，我们都计算，直接分别取其Math.max, Math.min， 如下：

max(n+1) = max(max(n) * arr[n+1], minus_max(n) * arr[n+1], arr[n+1])
minus_max(n+1) = min(max(n) * arr[n+1], minus_max(n) * arr[n+1], arr[n+1])

最终max(0), max(1), ...max(N)中的最大值即为所求

另，因为求max(n), minus_max(n)时都只与前一项（也就是max(n-1), minus_max(n-1)）有关，所以，无需存储长度为n的数组记录max(n)，或者minus_max(n)，而只需两个变量分别存储当前的max, minus_max.

代码如下：

function maxProduct(arr) {
    let max = arr[0];
    let minus_max = arr[0];
    let res = arr[0];
    const len = arr.length;

    for(let i=1; i < len; i++ ) {
        const max_tmp = max * arr[i];
        const minus_max_tmp = minus_max * arr[i];

        max = Math.max(max_tmp, minus_max_tmp, arr[i]);
        minus_max = Math.min(max_tmp, minus_max_tmp, arr[i]);
        res = max > res ? max : res;
    }
    return res;
}