Search This Blog

Sunday, October 5, 2014

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.
C++ Solution:
class Solution {
public:
    int maxProduct(int A[], int n) {
        int res = A[0];
        int pos = max(0, A[0]);
        int neg = min(0, A[0]);
        for (int i = 1; i < n; ++i) {
            if (A[i] == 0) {
                pos = 0;
                neg = 0;
            } else if (A[i] > 0) {
                pos = max(1, pos)*A[i];
                neg = neg*A[i];
            } else {
                int pos_old = pos;
                pos = neg*A[i];
                neg = min(A[i], A[i]*pos_old);
            }
            res = max(res, pos);
        }
        return res;
    }
};

No comments: