Maximum Product Subarray

max_prod.cc

class Solution {
public:
    int maxProduct(int A[], int n) {
        if (n == 0)
            return 0;
        // record both min values and max values. Use dp
        int max_pre = A[0];
        int min_pre = A[0];
        int max_value = A[0];
        int min_cur, max_cur;
        for (int ii = 1; ii < n; ++ii) {
            max_cur = std::max(A[ii], std::max(A[ii] * max_pre, A[ii] * min_pre));
            min_cur = std::min(A[ii], std::min(A[ii] * min_pre, A[ii] * max_pre));
            max_value = std::max(max_value, max_cur);
            max_pre = max_cur;
            min_pre = min_cur;
        }
        
        return max_value;
    }
};

max_prod_dp.cc

class Solution {
public:
    int maxProduct(int A[], int n) {
        // continuos subarray problem. Use dp. Start from the ith position
        if (n == 0)
            return 0;
        int *max_prod = new int[n];
        memset(max_prod, 0, sizeof(int) * n);
        int *min_prod = new int[n];
        memset(min_prod, 0, sizeof(int) * n);
        max_prod[n - 1] = min_prod[n - 1] = A[n - 1];
        int max_value = A[n - 1];
        for (int ii = n - 2; ii >= 0; --ii) {
            int prod_with_max = A[ii] * max_prod[ii + 1];
            int prod_with_min = A[ii] * min_prod[ii + 1];
            max_prod[ii] = std::max(A[ii], std::max(prod_with_max, prod_with_min));
            min_prod[ii] = std::min(A[ii], std::min(prod_with_max, prod_with_min));
            max_value = std::max(max_value, max_prod[ii]);
        }
        delete[] min_prod;
        delete[] max_prod;
        return max_value;
    }
};

max_sum.cc

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // continious subarray problem can be solved with dp
        // assume the subarray starts at i. And find the max value along the way
        if (n == 0)
            return 0;
            
        int *max_sum = new int[n]; // The maximum subarray that starts at i
        memset(max_sum, 0, sizeof(int) * n);
        max_sum[n - 1] = A[n - 1];
        int max_value = A[n - 1];
        for (int ii = n - 2; ii >= 0; --ii) {
            max_sum[ii] = std::max(max_sum[ii + 1] + A[ii], A[ii]);
            max_value = max_sum[ii] > max_value ? max_sum[ii] : max_value;
        }
        delete[] max_sum;
        return max_value;
    }
};