Maximum Product Subarray

18 July 2022

Maximum Product Subarray

If you are from 2023 batch student, Join our Telegram group for placement preparation and coming placement drive updates : https://t.me/talentbattle2023

Discription

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

#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

#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

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

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))

If you are from 2023 batch student, Join our Telegram group for placement preparation and coming placement drive updates : https://t.me/talentbattle2023