Maximum Product Subarray Solutions in C++

// Source : https://oj.leetcode.com/problems/maximum-product-subarray/
// Author : Hao Chen
// Date   : 2014-10-09



#include <iostream>
#include <algorithm>
using namespace std;

int max(int x, int y) {
    return x>y?x:y;
}
int min(int x, int y){
    return x<y?x:y;
}
int max(int x, int y, int z) {
    return max(x, max(y,z));
}
int min(int x, int y, int z) {
    return min(x, min(y, z));
}

// The idea is similar with "Find the subarray wich has the largest sum"
// (See: http://en.wikipedia.org/wiki/Maximum_subarray_problem)
// 
// The only thing to note here is, maximum product can also be obtained by minimum (negative) product 
// ending with the previous element multiplied by this element. For example, in array {12, 2, -3, -5, -6, -2}, 
// when we are at element -2, the maximum product is multiplication of, minimum product ending with -6 and -2.
//
int maxProduct(int A[], int n) {

    // To remember the max/min product for previous position
    int maxPrev = A[0], minPrev = A[0];
    // To remember the max/min product for current position
    int maxHere = A[0], minHere = A[0];
    // Overall maximum product
    int maxProd = A[0];

    for (int i=1; i<n; i++){
        maxHere = max( maxPrev * A[i], minPrev * A[i], A[i] );
        minHere = min( maxPrev * A[i], minPrev * A[i], A[i] );
        //Keep tracking the overall maximum product
        maxProd = max(maxHere, maxProd);
        //Shift the current max/min product to previous variables
        maxPrev = maxHere;
        minPrev = minHere;
    }
    return maxProd;    
}


#define TEST(a)    cout << maxProduct( a, sizeof(a)/sizeof(int)) << endl
int main()
{
    int o[] = {2,3,-2,4};
    TEST(o);

    int a[] = {-4,-3};
    TEST(a);

    int b[] = {-1, -1};
    TEST(b);

    int c[] = {-1, 0, -2};
    TEST(c);
}