Leetcode #152 Maximum Product Subarray

题目链接：https://leetcode.com/problems/maximum-product-subarray/

较麻烦的解法：

• 先判断数组中有没有0，有的话可以转换为求"0之前"和"0之后"两部分的较大值。

• 遍历，记录数组中负数的个数：  

  • 偶数：由于数组中都是整数，最大值即这些值的乘积。

  • 奇数：有以下几种可能，取它们中的最大值。

    • 第一个负数 / 最后一个负数。

    • 第一个负数之前的乘积 / 最后一个负数之前的乘积。

    • 第一个负数之后的乘积 / 最后一个负数之后的乘积。

官方 Solution 给出的解法：

Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.

Let us denote that:

           f(k) = Largest product subarray, from index 0 up to k. 

Similarly, 

           g(k) = Smallest product subarray, from index 0 up to k.

Then,

f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )

g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )

  

There we have a dynamic programming formula. Using two arrays of size n, we could deduce the final answer as f(n-1). Since we only need to access its previous elements at each step, two variables are sufficient.