Your friends have been studying the closest prices of tech stocks, looking for i

Question

Your friends have been studying the closest prices of tech stocks, looking for interesting patterns. They've defined something called a rising trend, as follows:

They have the closing price for a given stock recorded for n days in succession; let these prices be denoted P[1], P[2], …, P[n]. A rising trend in these prices is a subsequence of the prices P[i1], P[i2], …, P[ik] for days i1<i2<…<ik, so that

• i1 =1, and

Thus a rising trend is a subsequence of the days—beginning on the first day and not necessarily contiguous—so that the price strictly increases over the days in this subsequence. They are interested in finding the longest rising trend in a given sequence of prices.

Example. Suppose n = 7, and the sequence of prices is

10,1,2,11,3,4,12.

Then the longest rising trend is given by the prices on days 1, 4, and 7. Note that days 2, 3, 5, and 6 consist of increasing prices; but because this subsequence does not begin on day 1, it does not fit the definition of a rising trend.

(a) Show that the following algorithm does not correctly return the length of the longest rising trend, by giving an instance on which it fails to return the correct answer.

Define i=1

   L=1

For j=2 to n

If P[j] > P[i] then

Set i=j.

Add 1 to L.

Endif

Endfor

In your example, give the actual length of the longest rising trend, and say what the algorithm above returns.

(b) Give an efficient algorithm that takes a sequence of prices P[1], P[2], …, P[n] and returns the length of the longest rising trend.

Explanation / Answer

a) Created below code to test your algorithm:

#include <stdio.h>

int main()
{
int val[] = {10,3,4,5,6,3,2,4,2};
  
int i=0;
int L=1;
int j=1;
  
for(; j< 9; j++) {
if(val[j] > val[i]) {
i = j;
L++;
}
}
  
printf("Length: %d ", L);
return 0;
}

Output comes as Length 1, while There are other sequences present which have greater length than 1(such as 3,4,5,6 ). So Your algo is wrong, Because, your algo always start with the first element and then tries to compare other values with that. While, indeed, the sequence may not always start with value present at index 0.



Correct Algorithm:

Let arr[0..n-1] be the input array and L(i) be the length of the Longest rising trend ending at index i such that arr[i] is the last element of the Longest rising trend starting from arr[0].

Then, L(i), the length of longest trend can be written as(In recursive format):
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.. means L[i] is the maximum element encountered so far from a[0] to a[i]

To find the length of the longest rising trend for a given array, we need to return max(L(i)) where 0 < i < n.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.