Maximum Product Subarray

Time: O(n)

Space: O(1)

Intuition

Track both maximum and minimum product ending at each position (negative Ã— negative = positive). Max at each step = max of: current element alone, max*current, min*current.

Algorithm

1maxProd = minProd = result = nums[0].
2For each num from index 1: tmp = maxProd. maxProd = max(num, maxProd*num, minProd*num). minProd = min(num, tmp*num, minProd*num).
3result = max(result, maxProd).

Example Walkthrough

Input: [2,3,-2,4]

1.max=2,min=2. max=6,min=6. max=-2,min=-12. max=4,min=-48. Result=6.

Output: 6

Common Pitfalls

•Must track minimum product because negative Ã— negative = positive. Save tmp before updating maxProd.

Maximum Product Subarray.java

Java

// Approach: Track both max and min product ending here (negative * negative = positive).
// Update both at each step; update global max.
// Time: O(n) Space: O(1)
class Solution {
    // Function to find maximum product subarray
    int maxProduct(int[] arr) {
        int n = arr.length;
        int fpro = 1;
        int bpro = 1;
        int max = Integer.MIN_VALUE;
        for (int i = 0, j = n - 1; i < n; i++, j--) {
            fpro *= arr[i];
            bpro *= arr[j];

            if (bpro > max)
                max = bpro;

            if (fpro > max)
                max = fpro;

            if (fpro == 0)
                fpro = 1;

            if (bpro == 0)
                bpro = 1;

        }
        return max;
    }
}

Was this solution helpful?