Home > Free Resources > Coding Questions 2023 > Maximum Product Subarray

Maximum Product Subarray

06 May 2024

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

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

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

FAQ

Any Questions?
Look Here.

Related Articles

Program to identify if the character is an alphabet or not

Program to Replace substring in a string

Check if two strings match where one string contains wildcard characters

Lower Triangular Matrix

MATRIX MULTIPLICATION Program

Minimum Scalar Product Program

Program for Binary to decimal conversion

Program for Binary to octal conversion

Program for Decimal to binary conversion

Program for Decimal to octal conversion

Program for Maximum Scalar Product

Program for Octal to binary conversion

Program for Octal to decimal conversion

Program To Add two matrices and print the resultant matrix

Program to Add two fractions

Program to calculate Maximum number of handshakes

Program to calculate the Frequency of characters in a string

Program to Capitalize the first and last letter of each word of a string

Program to change the given matrix to transpose of the matrix.

Program to check if String is a palindrome or not

Program to check if two arrays are the same or not

Program to check if two strings are Anagram or not

Program to compare two strings

Program to concatenate a string

Program to copy a string

Program to Count common subsequence in two strings

Program to Count the sum of numbers in a string

Program to express a number as a sum of two prime numbers

Program to find Area of a rectangle

Program to find Area of a Triangle

Program to find ASCII values of a character

Program to find equilibrium index of an array

Program to find Factorial of a number

Program to find Fibonacci series up to n

Program to find Frequency of each element of an array

Program to find LCM of two numbers

Program to find longest palindrome in an array

Program to find minimum sum of absolute difference of given array

Program to find Number of days in a given month of a given year

Program to find Number of digits in an integer

Program to find number of even and odd elements in an array

Program to find number of integers which has exactly 9 divisors

Program to find Permutations in which n people can occupy r seats in a classroom.

Program to find Power of a number

Program to find roots of a quadratic equation

Program to find second smallest element in the array

Program to find smallest and largest element in an array

Program to find Sum of digits of a number

Program to find sum of elements in an array

Program to find Sum of N natural numbers

Program to find Sum of numbers in a given range

Program to find sum of positive square elements in the array

Program to find the Area of a circle

Program to find the array type

Program to find the double of the given number without using arithmetic operator

Program to find the Factors of a number

Program to find the Quadrants in which coordinates lie

Program to find whether an array is a subset of another array or not.

Program to find whether Arrays are disjoint or not

Program to find whether the numbers of an array be made equal

Program to identify if the character is a vowel or consonant

Program to identify if the number is Armstrong number or not

Program to identify if the number is even or odd

Program to identify if the number is Palindrome or not

Program to identify if the number is Perfect number or not

Program to identify if the number is Prime number or not

Program to identify if the number is Strong number or not

Program to identify of the a number is positive or negative

Program to print Armstrong numbers between two intervals

Program to print Diamond pattern printing using stars

Program to print Diamond pattern using Column number

Program to print Diamond pattern using Row numbers

Program to print Floyd’s triangle

Program to print hollow rectangle star pattern

Program to print Length of the string without using strlen() function

Program to print Non-repeating characters in a string

Program to print Palindromic pyramid pattern printing

Program to print Pascal triangle

Program to print prime numbers in a given range

Program to print Pyramid pattern using numbers

Program to print Pyramid pattern using stars

Program to print Solid rectangle star pattern

Program to print the length of a string

Program to print the max elements in all the rows.

Program to Remove brackets from an algebraic expression

Program to Remove characters in a string except alphabets

Program to remove duplicate elements in an array

Program to Remove spaces from a string

Program to Remove vowels from a string

Program to Replace all 0’s with 1 in a given integer

Program to reverse a given number

Program to reverse a string

Program to reverse the array

Program to sort the array

Program to Toggle each character in a string

Subtract matrix2 from matrix1 and print the resultant matrix program

Upper Triangular Matrix