Maximum Product Subarray

dp, three flavors of code are provided:

    //f[k] means maximum product that can be achieved ending with k
    //g[k] means minimum product that can be achieved ending with k

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

     int maxProduct3(int  A[],int n) {
        if (n<1)  return 0;
   
        vector<int> f(n,0),g(n,0);
        f[0] = A[0];
        g[0] = A[0];
        int res = A[0];
        for (int i = 1; i < n; i++) {
            f[i] = max(max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
            g[i] = min(min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
            res = max(res, f[i]);
        }
        return res;
    }

//convert the above one to use less space
    int maxProduct(int A[], int n) {
         if (n<1)  return 0;

        int f= A[0];
        int g= A[0];
        int res = A[0];
        for (int i = 1; i < n; i++) {
            int tmp=f;
            f = max(max(f * A[i], g* A[i]), A[i]);
            g = min(min(tmp * A[i], g* A[i]), A[i]);
            res = max(res, f);
        }
        return res;      
    }

//other flavors
    int maxProduct11(int A[], int n) {
        if (n < 1) return 0;
        int r = A[0];
        int max_p = A[0];
        // max_p is the maximum product that could be achieved
        // from the subarrays ending at the current position.
        int min_p = A[0];
        // The minimum product that could be achieved from
        // the subarrays ending at the current position.
        for(int i=1; i<n; i++){
            // The maximum or minimum product of the subarrays
            // ending at the current position could be achieved from the next three values.
            int a = max_p*A[i];
            // the max product of subarray ending at the previous position multiply the current value
            int b = min_p*A[i];
            // the minimum product of subarray ending at the previous position multiply the current value
            int c = A[i];
            // the current value
            max_p = max(max(a,  b),  c);
            min_p = min(min(a,  b),  c);
            if (max_p > r) r = max_p;
        }
        return r; 
    }
    //same idea way 2
    int maxProduct(int A[], int n) {
    if(n==1) return A[0];
    int pMax=0, nMax=0, m = 0;
    for(int i=0; i<n; i++){
        if(A[i]<0) swap(pMax, nMax);
        pMax = max(pMax*A[i], A[i]);
        nMax = min(nMax*A[i], A[i]);
        m = max(m, pMax);
    }
    return m;
    }