Maximum Product Subarray

07 January 2023

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

Related Articles

Ask Us Anything !