[LeetCode] Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

• 常规思路

class Solution {
public:
    int maxProduct(int A[], int n) {
        int product = INT_MIN;
        for (int i = 0; i < n; i++)
        {
            int sub = 1;
            for (int j = i; j < n; j++)
            {
                sub *= A[j];
                if (sub > product)
                {
                    product = sub;
                }
            }
        }

        return product;
    }
};

上述算法时间复杂度过高，LeetCode返回Time Limit Exceeded错误提示。

• 动态规划思路
  由于数组中有负数存在，一个负数乘以一个负数可能得到一个极大的正数，因此需要维护两个局部变量max_local和min_local。转移方程式如下：
  temp = max_local;
max_local[i] = max(max(max_local * A[i], min_local * A[i]), A[i]);
min_local[i] = min(min(temp * A[i], min_local * A[i]), A[i]);
• 实现代码

/*************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/8 21:43
    *  @Status   : Accepted
    *  @Runtime  : 13 ms
*************************************************************/
class Solution {
public:
    int maxProduct(int A[], int n) {
        if (n == 0)
        {
            return 0;
        }

        int max_local = A[0];
        int min_local = A[0];
        int global = A[0];
        for (int i = 1; i < n; i++)
        {
            int temp = max_local;
            max_local = max(max(max_local * A[i], min_local * A[i]), A[i]);
            min_local = min(min(temp * A[i], min_local * A[i]), A[i]);
            global = max(global, max_local);
        }

        return global;
    }
};