Maximum Product Subarray

Given an array of n integers, find the maximum product obtained from a contiguous subarray of the given array.

Examples

Input
arr[] = {-2, -3, 0, -2, -40}
Output
80

Input
arr[] = {5, 10, 6, -2, 1}
Output
300

Input
arr[] = {-1, -4, -10, 0, 70}
Output
70

Algorithm for Maximum Product Subarray

The given problem is a variation of Kadane’s Algorithm, define three variables maxTillNow, minTillNow and max, where,
maxTillNow –> Maximum Product up to this index, including this index
minTillNow –> Minimum Product up to this index, including this index
max –> The maximum product

1. Initialize maxTillNow, minTillNow and max as arr[0].
2. Traverse the array starting from index 1.
3. If the current element is negative swap maxTillNow and minTillNow.
4. Update maxTillNow as maximum of arr[i] and (maxTillNow * arr[i]).
5. Update minTillNow as minimum of arr[i] and (minTillNow * arr[i]).
6. Also, update max as a maximum of max and maxTillNow.
7. At the end of traversal, return max.

Explanation for Maximum Product Subarray

Consider an example,
arr[] = {5, 10, 6, -2, 1}

Step 1

maxTillNow = 5, minTillNow = 5 and max = 5

Step 2

Repeat steps 3 to 6.

Steps 3 to 6

Iteration 1
arr[1] = 10
maxTillNow = 5 and minTillNow = 5
Update maxTillNow,
maxTillNow = maximum(arr[1], maxTillNow * arr[1]) = 50
Update minTillNow,
minTillNow = minimum(arr[1], minTillNow * arr[1] = 10
Update max,
max = maximum(max, maxTillNow) = 50

Iteration 2
arr[2] = 6
maxTillNow = 50 and minTillNow = 10
Update maxTillNow,
maxTillNow = maximum(arr[2], maxTillNow * arr[2]) = 300
Update minTillNow,
minTillNow = minimum(arr[2], minTillNow * arr[2]) = 6
Update max,
max = maximum(max, maxTillNow) = 300

Iteration 3
arr[3] = -2
maxTillNow = 6 and minTillNow = 300 (Swap as arr[3] is negative)
Update maxTillNow,
maxTillNow = maximum(arr[3], maxTillNow * arr[3]) = -2
Update minTillNow,
minTillNow = minimum(arr[3], minTillNow * arr[3]) = -600
Update max,
max = maximum(max, maxTillNow) = 300

Iteration 4
arr[4] = 1
maxTillNow = -2 and minTillNow = -600
Update maxTillNow,
maxTillNow = maximum(arr[4], maxTillNow * arr[4]) = 1
Update minTillNow,
minTillNow = minimum(arr[4], minTillNow * arr[4]) = -600
Update max,
max = maximum(max, maxTillNow) = 300

Step 7

The maximum value product subarray value is 300.

JAVA Code for Maximum Product Subarray

public class MaximumProductSubarray {
    private static int maxProduct(int[] arr) {
        int n = arr.length;
        // Initialise maxTillNow, minTillNow and max as arr[0]
        int maxTillNow = arr[0], minTillNow = arr[0], max = arr[0];
        // Start traversing the array from index 1
        for (int i = 1; i < n; i++) {
            // If current element is negative, swap maxTillNow and minTillNow
            if (arr[i] < 0) {
                int temp = maxTillNow;
                maxTillNow = minTillNow;
                minTillNow = temp;
            }
            
            // Update maxTillNow as maximum of arr[i] and (arr[i] * maxTillNow)
            maxTillNow = Math.max(arr[i], arr[i] * maxTillNow);
            // Update minTillNow as minimum of arr[i] and (arr[i] * minTillNow)
            minTillNow = Math.min(arr[i], arr[i] * minTillNow);
            
            // Update max as maximum of max and maxTillNow
            max = Math.max(max, maxTillNow);
        }
        
        // return max
        return max;
    }

    public static void main(String[] args) {
        // Example 1
        int arr[] = new int[] {-2, -3, 0, -2, -40};
        System.out.println(maxProduct(arr));

        // Example 2
        int arr2[] = new int[] {5, 10, 6, -2, 1};
        System.out.println(maxProduct(arr2));

        // Example 3
        int arr3[] = new int[] {-1, -4, -10, 0, 70};
        System.out.println(maxProduct(arr3));
    }
}

C++ Code for Maximum Product Subarray

#include <bits/stdc++.h>
using namespace std;

int maxProduct(int *arr, int n) {
    // Initialise maxTillNow, minTillNow and max as arr[0]
    int maxTillNow = arr[0], minTillNow = arr[0], max = arr[0];
    // Start traversing the array from index 1
    for (int i = 1; i < n; i++) {
        // If current element is negative, swap maxTillNow and minTillNow
        if (arr[i] < 0) {
            int temp = maxTillNow;
            maxTillNow = minTillNow;
            minTillNow = temp;
        }
        
        // Update maxTillNow as maximum of arr[i] and (arr[i] * maxTillNow)
        maxTillNow = std::max(arr[i], arr[i] * maxTillNow);
        // Update minTillNow as minimum of arr[i] and (arr[i] * minTillNow)
        minTillNow = std::min(arr[i], arr[i] * minTillNow);
        
        // Update max as maximum of max and maxTillNow
        max = std::max(max, maxTillNow);
    }
    
    // return max
    return max;
}

int main() {
    // Example 1
    int arr[] = {-2, -3, 0, -2, -40};
    cout<<maxProduct(arr, 5)<<endl;
    
    // Example 2
    int arr2[] = {5, 10, 6, -2, 1};
    cout<<maxProduct(arr2, 5)<<endl;
    
    // Exmaple 3
    int arr3[] = {-1, -4, -10, 0, 70};
    cout<<maxProduct(arr3, 5)<<endl;
    
    return 0;
}

80
300
70

Complexity Analysis

Time Complexity = O(n)
Space Complexity = O(1) 
where n is the number of elements in the array.

References