A simple O(1) space O(n) time solution. Scan twice. From begin to end, then from end to begin.


  • 0
    J

    class Solution {
    public:
    int maxProduct(int A[], int n) {
    if (n == 1)
    return A[0];

    	int max = 0;
    	int acc = 1;
    	for (int i = 0; i < n; i++)
    	{
    		if (A[i] == 0)
    		{
    			acc = 1;
    			continue;
    		}
    		acc *= A[i];
    		if (acc > max)
    			max = acc;
    	}
    
    	acc = 1;
    	for (int i = n - 1; i >= 0; --i)
    	{
    		if (A[i] == 0)
    		{
    			acc = 1;
    			continue;
    		}
    		acc *= A[i];
    		if (acc > max)
    			max = acc;
    	}
    
    	return max;
    }
    

    };


  • 0
    I

    this won't work when u have multiple zeros to the left & right side of the max sub array


Log in to reply
 

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