[Google Question] Maximum Product Subarray

Problem: Find the contiguous sub-array within an array which has the largest product.

Solution: When the array has only positive elements then the product of all elements will be answer but when there are negative elements the problem becomes a bit complex. Following are the steps for solving this problem -

1. If current element is positive then max product can be achieved by multiplying current element with max product calculated so far.
2. If current element is negative then max product can be achieved by multiplying current element with min product calculated so far.
3. Current element might be a starting position for max product sub-array.

Implementation:

    public int MaxProduct(int[] nums) 

    {

        if (nums?.Length == 0)

        {

            return 0;        

        }

    

        int maxProduct = nums[0], minProduct = nums[0], result = nums[0];

        

        for (int i = 1; i < nums.Length; ++i)

        {

            int max = maxProduct * nums[i];

            int min = minProduct * nums[i];

            maxProduct = this.Max3(max, nums[i], min);

            minProduct = this.Min3(max, nums[i], min);

            result = Math.Max(result, maxProduct);

        }

        

        return result;

    }

    

    public int Max3(int x, int y, int z)

    {

        return Math.Max(Math.Max(x, y), z);

    }

    

    public int Min3(int x, int y, int z)

    {

        return Math.Min(Math.Min(x, y), z);

    }

Complexity: O(n)