Question

Let X = {x1,x2,...,xn} a sequence of real numbers. Design an algorithm that in linear time finds the continue subsequence of elements xi,xi+1,...,x, which product is the maximum. Suppose that the product of an empty subsequence is 1 and observe that the values can be less to 0 and less to 1.

Answer 1

#include <bits/stdc++.h>

using namespace std;

int max_product(int a[], int n)

{

int max_ending=1, min_ending=1;

int max_sofar=1, flag=0;

for(int i=0;i<n;i++)

{

//if the element is positive then multiply max_ending with the element

//in case min_ending is already negetive, multiplying it with positive element makes it even smaller

//flag is to mark that at least one positive value exist in the array

if(a[i]>0)

{

max_ending=max_ending*a[i];

min_ending=min(min_ending*a[i],1);

flag=1;

}

//if the element is zero the initialize the variables to 1 again since we have to find the continous sequence

//so we will be looking for a new subsequence from here

else if(a[i]==0)

{

max_ending=1;

min_ending=1;

}

//if the element is negetive then in case min_ending is negetive we multiply it with a[i] to get the positive product

//else one will be assigned to max_ending

//min_ending is then multiplied with the older value of max_ending(that was positive obviously) to get even smaller value---

//---since a[i] is negetive

else

{

int temp=max_ending;

max_ending=max(min_ending*a[i],1);

min_ending=temp*a[i];

}

//update max_sofar after each operation if required

if(max_sofar<max_ending)

max_sofar=max_ending;

}

//if there is an empty subsequence the returen 1. (As per the questions condition)

//(this can be modified to other condition as per requirement)

//else return max_sofar

if(flag==0 && max_sofar==1)

return 1;

return max_sofar;

}

int main()

{

cout<<"Enter the size of the array: ";

int n;

cin>>n;

int a[n];

cout<<"\nEnter the elements in the array: ";

for(int i=0;i<n;i++)

cin>>a[i];

cout<<"\nMax subarray product is: "<<max_product(a,n)<<endl; //call the max_product function to find the subarray with max product

return 0;

}