The Gateway to Computer Science Excellence
+1 vote
204 views
Given an array of ( both positive and negative ) integers, $a_0,a_1,….a_{n-1}$ and $l, 1<l<n$.

Design a linear time algorithm to compute the maximum product subarray, whose length is atmost $l$.
in Algorithms by Veteran (64.7k points) | 204 views

1 Answer

+1 vote

Algorithm:

 

1. When the array has only the positive numbers then the answer is simply the product of all of them.

2. In case of negative numbers, we have to adopt a different approach.

3. In case if the current element is positive, then the maximum product can be calculated by multiplying the current number with the maximum product calculated till now.

4. In case if the number is negative then maximum product can be obtained by multiplying the current number with the minimum product calculated so far.

5. For maximum product subArray, the current element may be a starting position.

Implementation:

//Implementation:

int max3(int a, int b, int c)
{
return a > b ? (a > c ? a : c) : (b > c ? b : c);
}

int min3(int a, int b, int c)
{
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

int maxProductSubArray(int arr[], int len)
{
if(len == 0)
return 0;
if(len == 1)
return arr[0];

int prevMax = arr[0], prevMin = arr[0];
int maxProduct = arr[0];
for(int i = 1; i < len; i++)
{
int currentMax = max3(prevMax * arr[i], prevMin * arr[i], arr[i]);
int currentMin = min3(prevMax * arr[i], prevMin * arr[i], arr[i]);
maxProduct = max(maxProduct, currentMax);
prevMax = currentMax;
prevMin = currentMin;
}
return maxProduct;
}

//Complexity: O(n)


Complexity: O(n)

 

by Boss (13.2k points)
edited by
0
This algorithm only calculates the maximum product sub-array of the given array and does not consider the part of the question where the length of the sub-array should be atmost $l$
0
It is covered in it.
0

No it is not covered, here you have considered $len$ as the length of the whole array, but here in the question it is asking what will be max-product if the max-product sub-array has length atmost $l$.For Ex: Given Array has elements : $1 ,2, 3, 4, 5$ and length of max product sub array given is 2 then the algo should give the output as $20(4*5)$ but your algo  gives output as $120$ for $len = 5$ and gives output $2$ for $len=2$.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,703 users