[LeetCode]Maximum Product Subarray

和max subarray的解法很类似，区别在这里负负可以得正，所以我们除了要记录局部最大值外还要记录局部最小值。首先我们定义几个变量，localMax[i]为以i结尾的subarray中最大的值，localMin[i]为以i结尾的subarray中最小的值；globalMax[i]定义为[0, i]范围中最大的subarray，globalMin[i]定义为[0, i]范围中最小的subarray，递推公式如下：

• if A[i] >= 0
• localMax[i] = max(localMax[i - 1] * A[i], A[i]);
• localMin[i] = min(localMin[i - 1] * A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);
• if A[i] < 0
• localMax[i] = max(localMin[i - 1] * A[i], A[i]);
• localMin[i] = min(localMax[i - 1] * A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);

可以开两个array来记录，不过可以优化到常数空间时间复杂度，时间复杂度O(n)，代码如下：