Share my O(n) C++ solution


  • 0
    H

    Basic idea is to keep the current largest positive product and smallest negative product. When we meet a negative number in the array, new largest positive is relevant to the last smallest negative product, vice versa.

    class Solution {
    public:
        int maxProduct(int A[], int n) {
            if (n==0) return 0;
            int pos = 0, nega = 0, ans = A[0];
            if (A[0]>0) pos = A[0]; else nega = A[0];
            for (int i = 1; i<n; i++)
            {
                if (A[i]>0)
                {
                    if (pos>0) pos*=A[i]; else pos = A[i];
                    nega*=A[i];
                }
                else
                {
                    int temp = nega;
                    if (pos>0) nega = pos*A[i]; else nega = A[i];
                    pos = temp*A[i];   
                }
                if (pos>0 || A[i]==0) ans = max(ans, pos);
            }
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.