In class, we solved the maximum subsequence sum problem. In that problem, you we
ID: 3842151 • Letter: I
Question
In class, we solved the maximum subsequence sum problem. In that problem, you were given an input array A = [ a1, a2,…. an] I containing real numbers. You had to find the contiguous subsequence with the greatest sum. A contiguous subsequence is a subsequence from A that does not skip elements from A: in other words, it is a subsequence ai, ai+l, ai+2, ai+3……aj-2, aj-3, aj that contains all elements from A that occur between the i-th and j-th elements (e.g., a5, a6, a7, a8 is a contiguous subsequence, but a5, a6, a7, a8 is not).
Your challenge in this problem is to solve the maximum subsequence product problem. This problem is identical to the maximum subsequence sum problem, except now you want to find the contiguous subsequence with the greatest product ai X ai+1 X….X ak. Assume all values in the array are positive. Design a dynamic programming algorithm to solve this problem.
In other words, design a function MaxSubSequenceProduct (array A) that returns indices i and j, such that I <= j. The subsequence A[i,….j] = ai, ai+1,……, aj-1, aj should b the contiguous subsequence that has the greatest product ai X ai+1 X…..X ak of all the contiguous subsequences from A.
What is your function's running time?
Explanation / Answer
The algorithm is as follows:
As per the question we can assume that array contains all the positive numbers
If the list contains all the positive numbers greater than 0, then product of all the numbers will give the the maximum
product, this is of O(n). We need to perform multuplication n times.
If the list containg numbers equal to 0 also, then we need to change the approach:
Lets us say max_product = 1 (Initialized)
We start from index 0, if a[0] = 0, we will change the starting index to be 1, so our serarch will start with the first
non zero entity. We will obtaing the product as max_product * a[i] where i is the index of first non zero entity.
We will keep on going updating the product with a[i+1] onwards till we get a zero entry. As soon as we encounter 0 we have
to start a new search from the next element onwards. We will store the previous i, j , max_product. Now we will again doing the same thing with initialization of max_product to 1 and keep on updating it as we traverse through elements.If we again get 0, we need to update the previously stored i, j, maxproduct only if current value of max_product will be more, otherwise we need to keep the old values as it is. We need to do this till we reach the end of the list and only updating
i, j, max_product only if we current max_product is more than the previous max_product.
As we are traversing the array element by element and performing opeartions, this will be of order n i.e O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.