Max Product Subarray

• Time : $O(n)$
• Space : $O(1)$

int Solution::maxProduct(const vector<int> &A) {
    int res = INT_MIN;
    int all = 1, n = A.size(), st = 0;
    for(int i = 0; i <= n; i++) {
        if(i == n or A[i] == 0) {
            if(A[i] == 0) res = max(res, 0);
            if(st == i) {}
            else if(all > 0) res = max(res, all);
            else {
                int left = 1, right = 1;
                for(int j = st; left > 0; j++) left *= A[j];
                for(int j = i - 1; right > 0; j--) right *= A[j];
                if(left == all) res = max(res, all);
                else res = max(res, all / left);
                if(right == all) res = max(res,all);
                else res = max(res, all / right);
            }
            all = 1;
            st = i + 1;
        } else all *= A[i];
    }
    return res;
}