My solution - O(1) space O(n) time - just doing a summary


  • 2
    Q

    observations:

    1. the optimum sub-array has no 0 in it;
    2. for an array with no 0, the optimum sub-array starts from either the first number or from the number after first negative number (the numbers in front of it constitutes the firs negative factor).

    my approach:

    1. break the array into chunks separated by zeros;
    2. for each chunk, find the maximum value of 2 sequences products:
      I. products of the contiguous sub-arrays starting from the 1st number of the chunk;
      II. products of the contiguous sub-arrays starting from the number after the 1st negative number in the chunk;
    3. the answer is the maximum of the results from all chunks and 0.

    code:

    class Solution {public:
    int maxProduct(int A[], int n) {
        int p1, p2, nn, max;
        p1 = 1, nn = 0, max = A[0];
        for(int i = 0; i < n; i++) {
            if(A[i] == 0) {
                p1 = 1;
                nn = 0;
                if(max < 0) max = 0;
            } else {
                p1 *= A[i];
                if(p1 > max) max = p1;
                if(nn) {
                    p2 *= A[i];
                    if(p2 > max) max = p2;
                }
                if(A[i] < 0 and !nn) {
                    p2 = 1;
                    nn = 1;
                }
            }
        }
        return max;
    }
    

    };


Log in to reply
 

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