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++:

int maxProduct(vector<int>& a) {
    int result = INT_MIN;
    for(int i=0;i<a.size()-1;i++) {
        for(int j=i+1;j<a.size();j++) {
            int p = 1;
            for(int k=i;k<=j;k++)
                p*= a[k];
            result = max(result,p);
        }
    }
    return result;
}

Java:

 int maxProductS(int a[]) {
	    int result = Integer.MIN_VALUE;
	    for(int i=0;i<a.length-1;i++)
	        for(int j=i+1;j<a.length;j++) {
	            int p = 1;
	            for(int k=i;k<=j;k++)
	                prod *= a[k];
	            result = Math.max(result,p);
	        }
	   return result;
	}

Python:

def maxSubarray(a, n):
    result = a[0]
    for i in range(n):
        m = a[i]
        for j in range(i + 1, n):
            result = max(result, m)
            m *= a[j]
        result = max(result, m)
    return result

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++:

int maxProduct(vector<int>& a) {
    int result = nums[0];
    for(int i=0;i<a.size()-1;i++) {
        int p = a[i];
        for(int j=i+1;j<a.size();j++) {
           result = max(result,p);
           p *= a[j];
        }
        result = max(result,p);//manages (n-1)th term
    }
    return result;
}

Java:

static int maxProduct(int a[]) {
	    int result = a[0];
	    for(int i=0;i<a.length-1;i++) {
	        int p = a[i];
	        for(int j=i+1;j<a.length;j++) {
	            result = Math.max(result,p);
	            p *= a[j];
	        }
	        result = Math.max(result,p);
	    }
	   return result;
	}

Python:

def maxProduct(a):
  res=a[0]
  for i in range(0,len(a)):
    p=a[i]
    for j in range(i+1,len(a)):
      res=max(res,p)
      p=p*a[j]
    res=max(res,p)
  return res

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++:

vector < vector < int >> maxProduct(vector < vector < int >> & a) {
  sort(a.begin(), a.end());

  vector < vector < int >> m;
  for (auto interval: intervals) {
    if (m.empty() || m.back()[1] < a[0]) {
      m.push_back(a);
    } else {
      m.back()[1] = max(m.back()[1], a[1]);
    }
  }
  return m;
}

Java:

int maxProduct(vector < int > a) {
  if (a.size() == 0) return 0;

  int max_so_far = a[0];
  int min_so_far = a[0];
  int result = max_so_far;

  for (int i = 1; i < a.size(); i++) {
    int curr = a[i];
    int temp_max = max(curr, Math.max(max_so_far * curr, min_so_far * curr));
    min_so_far = min(curr, Math.min(max_so_far * curr, min_so_far * curr));

    max_so_far = temp_max;

    result = max(max_so_far, result);
  }

  return result;
}

Python:

def maxProduct(self, a: List[int]) -> int:
    if len(a) == 0:
        return 0

    max_so_far = a[0]
    min_so_far = a[0]
    result = max_so_far

    for i in range(1, len(a)):
        curr = a[i]
        temp_max = max(curr, max_so_far * curr, min_so_far * curr)
        min_so_far = min(curr, max_so_far * curr, min_so_far * curr)

        max_so_far = temp_max

        result = max(max_so_far, result)

    return result

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++:

int maxProduct(vector<int>& a) {
    int maxLeft = a[0];
    int maxRight = a[0];

    int p = 1;

    bool zero =  false;

    for(auto i:a) {
        p *= i;
        if(i == 0) {
            zero = true;
            p = 1;
            continue;
        }
        maxLeft = max(maxLeft,p);
    }

    p = 1;

    for(int j=a.size()-1;j>=0;j--) {
        p *= a[j];
        if(a[j] == 0) {
            zero = true;
            p = 1;
            continue;
        }
        maxRight = max(maxRight,p);
    }

    if(zero) return max(max(maxLeft,maxRight),0);
    return max(maxLeft,maxRight);
}

Java:

static int maxProductSubArray(int a[]) {
	    int maxLeft = a[0];
	    int maxRight = a[0];

	    boolean zero = false;

	    int p = 1;

	    for(int i:a) {
	        p *= i;
	        if(i == 0) {
	            zero = true;
	            p = 1;
	            continue;
	        }
	        maxLeft = Math.max(maxLeft,p);
	    }

	    p = 1;

	    for(int j=a.length-1;j>=0;j--) {
	        p *= a[j];
	        if(a[j] == 0) {
	            zero = true;
	            p = 1;
	            continue;
	        }
	        maxRight = Math.max(maxRight,p);
	    }

	    if(zero) return Math.max(Math.max(maxLeft,maxRight),0);
	    return Math.max(maxLeft,maxRight);
	}

Python:

def max_product(arr, n):

    max_fwd = -sys.maxsize - 1
    max_bkd = -sys.maxsize - 1

    max_till_now = 1

    for i in range(n):

        max_till_now = max_till_now * arr[i]
        if (max_till_now == 0):
            isZero=True
            max_till_now = 1;
            continue

        if (max_fwd < max_till_now): #update max_fwd
            max_fwd = max_till_now

    max_till_now = 1

    for i in range(n - 1, -1, -1):
        max_till_now = max_till_now * arr[i]

        if (max_till_now == 0):
            isZero=True
            max_till_now = 1
            continue

        if (max_bkd < max_till_now) :
            max_bkd = max_till_now

    res = max(max_fwd, max_bkd)

    if isZero==True :
        return max(res, 0)

    return res

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++:

int maxProduct(vector<int>& a) {
    int prod1 = a[0],prod2 = a[0],result = a[0];

    for(int i=1;i<a.size();i++) {
        int temp = max({a[i],prod1*a[i],prod2*a[i]});
        prod2 = min({a[i],prod1*a[i],prod2*a[i]});
        prod1 = temp;

        result = max(result,prod1);
    }

    return result;
}

Java:

static int maxProduct(int a[]) {
    int prod1 = a[0],prod2 = a[0],result = a[0];

    for(int i=1;i<a.length;i++) {
        int temp = Math.max(a[i],Math.max(prod1*a[i],prod2*a[i]));
        prod2 = Math.min(a[i],Math.min(prod1*a[i],prod2*a[i]));
        prod1 = temp;

        result = Math.max(result,prod1);
    }

    return result;
	}

Python:

def maxProduct(self, nums: List[int]) -> int:
        res = max(nums)
        curMin, curMax = 1, 1

        for n in nums:
            if n == 0:
                curMin, curMax = 1, 1
                continue

            temp = n * curMax
            curMax = max(n * curMax, n * curMin, n)
            curMin = min(temp, n * curMin, n)
            res = max(res, curMax)

        return res

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.

Conclusion

• In Brute force, we find all possible subarrays of the given array. Find the product of each subarray. Return the maximum of all of them.
• We then optimized the brute force by making 33 nested iterations to 22 nested iterations.
• Two traversals can also be used to solve this issue. Here, we will use two local maximum values to traverse from left to right or from index 00 to n−1n−1 to obtain the maximum product.
• The most effective way to solve the problem is through dynamic programming. O(N)O(N) is the time complexity, and O(1)O(1) is the space complexity .