Max Product Subarray

Difficulty: Medium

Asked in: Amazon, Microsoft

Understanding The Problem

Problem Description

You are given an array arr[] with n elements. Write a program to find the contiguous subarray which has the largest product.

Problem Note

A contiguous subarray of an array arr[] of length n is a contiguous segment from arr[i] through arr[j] where 0<= i <= j <= n .
Array arr[] may contain both positive and negative integers. If the array contains all non-negative numbers, the maximum subarray is the product of the entire array.

Example 1

Input: arr[] = [9, -6, 10, 3] 
Output: 30 
Explanation: The subarray [10, 3] has the maximum product.

Example 2

Input: arr[] = [6, -3, -10, 0, 2] 
Output: 180  
Explanation: The subarray [6, -3, -10] has the maximum Product.

Example 3

Input: arr[] = [-2, -3, 0, -2, -40] 
Output:  80  
Explanation: The subarray [-2, -40] has the maximum product.

Solutions

Brute Force: Find all the subarray products and return the maximum.
Dynamic Programming: Keep track of the minimum and maximum products while scanning arr .

You may try the problem here.

1. Brute Force

To find the maximum product of a subarray in the given array we can calculate for all the possible products and return the maximum.

Solution Step

Create maxProduct to store the maximum subarray product.
For every pair of integers (i, j) in the range size(arr)
Calculate the product of arr[i . . . j] and update maxProduct .

Pseudo Code

int maxSubArrayProduct(int[] arr, int size) {
    int maxProduct = INT_MIN
    for(int i=0 to i < size){
        localProduct = 1
        for(int j=i to j < size){
            localProduct = localProduct * arr[j]
        }
        maxProduct = max(maxProduct, localProduct)
    }
    return maxProduct
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(1)

Critical Ideas To Think

Why we initialized localProduct with 1?
What if we initialized maxProduct with 1?
Dry run this on some sample test cases and try to optimize the solution.

2. Dynamic Programming

Imagine that we have both max_prod[i] and min_prod[i] i.e. max product ending at i and min product ending at i .

Now if we have a negative number at arr[i+1] and if min_prod[i] is negative, then the product of the two will be positive and can potentially be the largest product. So, the key point here is to maintain both the max_prod and min_prod such that at iteration i , they refer to the max and min product ending at index i-1 .

In short, One can have three options to make at any position in the array.

You can get the maximum product by multiplying the current element with the maximum product calculated so far. (might work when current
element is positive).
You can get the maximum product by multiplying the current element with minimum product calculated so far. (might work when current
element is negative).
The current element might be a starting position for maximum product subarray.

Solution Steps

Initialize maxProduct with arr[0] to store the maximum product so far.
Initialize to variables imax and imin to store the maximum and minimum product till i .
Iterate over the arr and for each negative element of arr, swap imax and imin . (Why?)
Update imax and imin as discussed above and finally return maxProduct

Pseudo Code

int maxSubArrayProduct(int[] arr, int size) {
    int maxProduct = arr[0]
    int imax = arr[0]
    int imin = arr[0]
    for(int i=1 to i<size) {
        if(arr[i]<0) 
            swap(imax,imin)
        imax = max(arr[i], imax * arr[i])
        imin = min(arr[i],imin * arr[i])
        maxProduct = max(maxProduct, imax)
    }
    return maxProduct
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas To Think

What if the array has just positive numbers including zero?
If we store the prefix product of arr say pref_arr and the suffix product of arr say suf_arr and then return the maximum of pref_arr and suf_arr , will the solution work? If yes, then do you think that the above-discussed approach is analogous to it?