Share my O(n) C++ solution

  • 0

    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 {
        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];
                    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.