Maximum Product Subarray by Traverse Over Every Contiguous Subarray
The idea is to traverse over every contiguous subarray, find the product of each of these subarrays and return the maximum product from these results.
Follow the below steps to solve the problem:
- Run a nested for loop to generate every subarray
- Calculate the product of elements in the current subarray
- Return the maximum of these products calculated from the subarrays
Below is the implementation of the above approach:
// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
/* Returns the product of max product subarray.*/
int maxSubarrayProduct(int arr[], int n)
{
// Initializing result
int result = arr[0];
for (int i = 0; i < n; i++) {
int mul = arr[i];
// traversing in current subarray
for (int j = i + 1; j < n; j++) {
// updating result every time
// to keep an eye over the maximum product
result = max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = max(result, mul);
}
return result;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Sub array product is "
<< maxSubarrayProduct(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
// C program to find Maximum Product Subarray
#include <stdio.h>
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
/* Returns the product of max product subarray.*/
int maxSubarrayProduct(int arr[], int n)
{
// Initializing result
int result = arr[0];
for (int i = 0; i < n; i++) {
int mul = arr[i];
// traversing in current subarray
for (int j = i + 1; j < n; j++) {
// updating result every time
// to keep an eye over the maximum product
result = max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = max(result, mul);
}
return result;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Maximum Sub array product is %d ",
maxSubarrayProduct(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
// Java program to find maximum product subarray
import java.io.*;
class GFG {
/* Returns the product of max product subarray.*/
static int maxSubarrayProduct(int arr[])
{
// Initializing result
int result = arr[0];
int n = arr.length;
for (int i = 0; i < n; i++) {
int mul = arr[i];
// traversing in current subarray
for (int j = i + 1; j < n; j++) {
// updating result every time to keep an eye
// over the maximum product
result = Math.max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = Math.max(result, mul);
}
return result;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
System.out.println("Maximum Sub array product is "
+ maxSubarrayProduct(arr));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
# Python3 program to find Maximum Product Subarray
# Returns the product of max product subarray.
def maxSubarrayProduct(arr, n):
# Initializing result
result = arr[0]
for i in range(n):
mul = arr[i]
# traversing in current subarray
for j in range(i + 1, n):
# updating result every time
# to keep an eye over the maximum product
result = max(result, mul)
mul *= arr[j]
# updating the result for (n-1)th index.
result = max(result, mul)
return result
# Driver code
arr = [1, -2, -3, 0, 7, -8, -2]
n = len(arr)
print("Maximum Sub array product is", maxSubarrayProduct(arr, n))
# This code is contributed by divyeshrabadiya07
// C# program to find maximum product subarray
using System;
class GFG {
// Returns the product of max product subarray
static int maxSubarrayProduct(int[] arr)
{
// Initializing result
int result = arr[0];
int n = arr.Length;
for (int i = 0; i < n; i++) {
int mul = arr[i];
// Traversing in current subarray
for (int j = i + 1; j < n; j++) {
// Updating result every time
// to keep an eye over the
// maximum product
result = Math.Max(result, mul);
mul *= arr[j];
}
// Updating the result for (n-1)th index
result = Math.Max(result, mul);
}
return result;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
Console.Write("Maximum Sub array product is "
+ maxSubarrayProduct(arr));
}
}
// This code is contributed by shivanisinghss2110
<script>
// Javascript program to find Maximum Product Subarray
/* Returns the product of max product subarray.*/
function maxSubarrayProduct(arr, n)
{
// Initializing result
let result = arr[0];
for (let i = 0; i < n; i++)
{
let mul = arr[i];
// traversing in current subarray
for (let j = i + 1; j < n; j++)
{
// updating result every time
// to keep an eye over the maximum product
result = Math.max(result, mul);
mul *= arr[j];
}
// updating the result for (n-1)th index.
result = Math.max(result, mul);
}
return result;
}
// Driver code
let arr = [ 1, -2, -3, 0, 7, -8, -2 ];
let n = arr.length;
document.write("Maximum Sub array product is "
+ maxSubarrayProduct(arr, n));
// This code is contributed by Mayank Tyagi
</script>
Time Complexity: O(N2)
Auxiliary Space: O(1)
Maximum Product Subarray
Given an array that contains both positive and negative integers, the task is to find the product of the maximum product subarray.
Examples:
Input: arr[] = {6, -3, -10, 0, 2}
Output: 180
Explanation: The subarray is {6, -3, -10}Input: arr[] = {-1, -3, -10, 0, 60}
Output: 60
Explanation: The subarray is {60}
Contact Us