Maximum Product Subarray

Problem Statement

You are given a list of integers. Your task is to find and print the contiguous non-empty subarray that produces the largest product when multiplied together.

A subarray is a sequence of consecutive and uninterrupted elements within an array.

Example

If Array = { -2, 6, 4 } All the possible non-empty contiguous subarrays of Array are {-2}, {4}, {6}, {-2,4}, {4,6} and {-2,6,4}.

The product of these subarrays are $-2, 4, 6, -8, 24$ and $-48$ respectively.

The maximum product is $24$. Hence, the answer is $24$.

Approach - 1 : Simple Brute Force Approach

Find every possible subarray for the provided array. Find the product of each subarray. Give back the highest value among them.

The steps for the approach are as follows :

• To select the beginning of each subarray, run a loop across the array.
• Run a' nested loop' to determine the endpoint for each subarray.
• Multiply the range-containing elements.

Code Implementation

C++:

Java:

Python:

Time Complexity

The Time Complexity of the Simple Brute Force Approach is O(N^3) because We are using $3$ nested loops for finding all possible subarrays and their product.

Space Complexity

The Space Complexity of the Simple Brute Force Approach is O(1).

Approach - 2 : Optimized Brute Force Approach

We can improve the brute force method by reducing the number of nested iterations from three to two.

The steps for the approach are as follows:

• To locate the beginning of the subarrays, execute a loop.
• Add one more nested loop.
• Each element should be multiplied, and the subarray's maximum value should be stored.

Code Implimentation

C++:

Java:

Python:

Time Complexity

The Time Complexity of the Optimized Brute Force Approach is O(N^2) because we are using two nested loops.

Space Complexity

The Space Complexity of Optimized Brute Force Approach is O(1), As no extra data structures are used for computation.

Approach - 3 : Efficient Dynamic Programming Approach

Algorithm :

• Create a variable result = $A[0]$ and initialize it to hold the maximum product.
• Two variables max so far and min so far, which represent the highest and lowest product so far, should be initialized with $A[0]$.
• Swap max so far and min so far for negative elements as you traverse the input array.
• max so far should be maximised and updated with max so $far * A[i]$.
• Update it with min so $far * A[i]$ after minimising min so far.
• maximum of max so far and a minimum of min so far updated the result.
• return result for maximum product subarray.

Code Implementation

C++:

Java:

Python:

Time Complexity

The Time Complexity of Optimized Brute Force Approach is O(N), where N is the total size of the array.

Space Complexity

The Space Complexity of Optimized Brute Force Approach is O(1).

Approach - 4 : Two Traversals

The goal is to locate the maximum product subarray from both angles or once moving forward and once moving backwards.

Steps

• Once from left to right iteration to produce the best possible result for forwarding motion.
• We return all variables to their initial values if zero is detected.
• Once more, iterate from right to left to produce the best possible result for the reverse direction.
• If zero is found, we reset all variables to zero once more to locate a new subarray with the highest product.
• The maximum product produced from both iterations is the overall result for the maximum product subarray of the supplied array once both iterations have been completed.

Code Implementation

C++:

Java:

Python:

Time Complexity

The Time Complexity of the Optimized Brute Force Approach is O(N) because we are iterating two times to compute the maximum product.

Space Complexity

The Space Complexity of Optimized Brute Force Approach is O(1), As no extra data structures are used for computation.

Approach - 5 : Kadane's Algorithm

The best part about this approach is that we can produce the largest amount of the product while multiplying two negative values.

The approach's steps are as follows:

• Go through the array.
• We'll keep prod1 and prod2 for every element.
• Prod1 is the greatest of the current element, prod1 and prod2, and the current element and prod2.
• Prod2 is the minimum of the current element, prod1 and prod2, and the current element and prod2.
• return maximum among results and prod1.

Code Implementation

C++:

Java:

Python:

Time Complexity

The Time Complexity of Kadane's Algorithm for calculating the maximum product subarray is $O(N)$ because A single iteration is used.

Space Complexity

The Space Complexity of Kadane's Algorithm is O(1), As no extra data structure is used for computation.