Description about Maximum Product Subarray
Sample input 1:
4
2 -4 -1 -3
Sample output 1:
8 = {2, -4, -1}
Sample input 2:
5
1 5 -7 5 3
Sample output 2:
15 = {5, 3}
Solution:
C Program for Maximum Product Subarray
#include <stdio.h>
int MaxSubArrProd(int *arr, int n)
{
int ans = arr[0];
for (int i = 0; i < n; i++)
{
int prod = arr[i];
for (int j = i + 1; j < n; j++)
{
ans = ans > prod ? ans : prod;
prod =prod * arr[j];
}
ans = ans > prod ? ans : prod;
}
return ans;
}
int main()
{
int n; scanf("%d",&n);
int arr[n];
for(int i = 0 ; i<n ; i++)
{
scanf("%d",&arr[i]);
}
printf("%d",MaxSubArrProd(arr,n));
return 0;
}
C++ Program for Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
int MaxSubArrProd(int arr[], int n)
{
int ans = arr[0];
for (int i = 0; i < n; i++)
{
int prod = arr[i];
for (int j = i + 1; j < n; j++)
{
ans = max(ans,prod);
prod =prod * arr[j];
}
ans = max(ans,prod);
}
return ans;
}
int main()
{
int n; cin>>n;
int arr[n];
for(int i = 0 ; i<n ; i++)
{
cin>>arr[i];
}
cout<<MaxSubArrProd(arr,n);
return 0;
}
JAVA Program for Maximum Product Subarray
import java.util.*;
class Main
{
static int MaxSubArrProd(int arr[], int n)
{
int ans = arr[0];
for (int i = 0; i < n; i++)
{
int prod = arr[i];
for (int j = i + 1; j < n; j++)
{
ans = Math.max(ans,prod);
prod =prod * arr[j];
}
ans = Math.max(ans,prod);
}
return ans;
}
public static void main(String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i = 0 ; i<n ; i++)
{
arr[i] = sc.nextInt();
}
System.out.print(MaxSubArrProd(arr,n));
}
}
PYTHON Program for Maximum Product Subarray
def MaxSubArrProd(arr,n):
ans = arr[0]
for i in range(0,n):
prod = arr[i]
for j in range(i+1,n):
ans = max(ans,prod)
prod =prod * arr[j]
ans = max(ans,prod)
return ans;
n = int(input())
arr = list(map(int,input().split(' ')))
print(MaxSubArrProd(arr,n))
