Maximum Product Subarray using Kadane’s Algorithm
The idea is to use Kadane’s algorithm and maintain 3 variables max_so_far, max_ending_here & min_ending_here. Iterate the indices 0 to N-1 and update the variables such that:
- max_ending_here = maximum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i])
- min_ending_here = minimum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i])
- update the max_so_far with the maximum value for each index.
return max_so_far as the result.
Follow the below steps to solve the problem:
- Use 3 variables, max_so_far, max_ending_here & min_ending_here
- For every index, the maximum number ending at that index will be the maximum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i])
- Similarly, the minimum number ending here will be the minimum of these 3
- Thus we get the final value for the maximum product subarray
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)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending previously
and the min product ending previously. */
for (int i = 1; i < n; i++) {
int temp = max({ arr[i], arr[i] * max_ending_here,
arr[i] * min_ending_here });
min_ending_here
= min({ arr[i], arr[i] * max_ending_here,
arr[i] * min_ending_here });
max_ending_here = temp;
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
// 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;
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
/* Returns the product of max product subarray. */
int maxSubarrayProduct(int arr[], int n)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending previously
and the min product ending previously. */
for (int i = 1; i < n; i++) {
int temp
= max(max(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
min_ending_here
= min(min(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
// 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)
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Java program to find Maximum Product Subarray
// Returns the product
// of max product subarray.
static int maxSubarrayProduct(int arr[], int n)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
// /* Traverse through the array.
// the maximum product subarray ending at an index
// will be the maximum of the element itself,
// the product of element and max product ending
// previously and the min product ending previously.
// */
for (int i = 1; i < n; i++) {
int temp = Math.max(
Math.max(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
min_ending_here = Math.min(
Math.min(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far
= Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver code
public static void main(String args[])
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
int n = arr.length;
System.out.printf("Maximum Sub array product is %d",
maxSubarrayProduct(arr, n));
}
}
// This code is contributed by shinjanpatra
# Python3 program to find Maximum Product Subarray
# Returns the product
# of max product subarray.
def maxSubarrayProduct(arr, n):
# max positive product
# ending at the current position
max_ending_here = arr[0]
# min negative product ending
# at the current position
min_ending_here = arr[0]
# Initialize overall max product
max_so_far = arr[0]
# /* Traverse through the array.
# the maximum product subarray ending at an index
# will be the maximum of the element itself,
# the product of element and max product ending previously
# and the min product ending previously. */
for i in range(1, n):
temp = max(max(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here)
min_ending_here = min(
min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here)
max_ending_here = temp
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
# Driver code
arr = [1, -2, -3, 0, 7, -8, -2]
n = len(arr)
print(f"Maximum Sub array product is {maxSubarrayProduct(arr, n)}")
# This code is contributed by shinjanpatra
// C# program to find maximum product subarray
using System;
class GFG {
/* Returns the product of max product subarray.
Assumes that the given array always has a subarray
with product more than 1 */
static int maxSubarrayProduct(int[] arr)
{
// max positive product
// ending at the current position
int max_ending_here = arr[0];
// min negative product ending
// at the current position
int min_ending_here = arr[0];
// Initialize overall max product
int max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending
previously and the min product ending previously. */
for (int i = 1; i < arr.Length; i++) {
int temp = Math.Max(
Math.Max(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
min_ending_here = Math.Min(
Math.Min(arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far
= Math.Max(max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
Console.WriteLine("Maximum Sub array product is "
+ maxSubarrayProduct(arr));
}
}
// This code is contributed by CodeWithMini
<script>
// JavaScript program to find Maximum Product Subarray
/* Returns the product
of max product subarray. */
function maxSubarrayProduct(arr, n)
{
// max positive product
// ending at the current position
let max_ending_here = arr[0];
// min negative product ending
// at the current position
let min_ending_here = arr[0];
// Initialize overall max product
let max_so_far = arr[0];
/* Traverse through the array.
the maximum product subarray ending at an index
will be the maximum of the element itself,
the product of element and max product ending previously
and the min product ending previously. */
for (let i = 1; i < n; i++)
{
let temp = Math.max(Math.max(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
min_ending_here = Math.min(Math.min(arr[i], arr[i] * max_ending_here), arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
// 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 shinjanpatra
</script>
Output
Maximum Sub array product is 112
Time Complexity: O(N)
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