The logic of this question

[Avatar19]

Hi there, I am not really asking for help in terms of a programming solution but rather if anyone is able to explain the logic of this question to me cause i really cannot make sense of this!!!!
Here it is:

Introduction
For reasons understood only by stock-brokers, one of the
signs of a good stock trading strategy is to always buy a
stock for less than one previously bought it for.

Task
You’ve been asked to help measure the performance of
some stock-brokers by looking at the history of prices for
a stock. You will be provided with a list of prices, and
must determine the maximum number of times this stock
could have been bought while paying strictly less for it
each time

Example
Suppose that a stock has had historical prices of R10,
R5, R30, R25, R23, R25, R20, R24 and R22. Then the
maximum number of times it could be bought would be
4, buying it for R30, R25, R24 and R22. Notice that the
price must strictly decrease each time, so it cannot be
bought twice for R25.
Example
R1, R5 can be bought only 1 time.

The actual programming of this looks pretty simple but the logic of what they are asking just doesn't make sense to me so please help explain it if you can!
Thanks a lot
Ava19

[jkmyoung]

I don't get what you mean by the logic of it.
If your solution is buy at R10, R22, then it is an invalid solution, since 10 < 22.

A. Brute force method:
Take all possibilities of buying.
Eliminate the ones that aren't possible.
Take the longest possibility.

B. Depth first search method. (form of greedy algorithm)
Buy at the first chance you can get.
Continue buying each one that you can.
When you get to the end, store the result and, recurse back to the last one you bought, don't buy that one, and try rerunning on the rest to improve your result.

B2. Depth first search method from the back. Same but reverse order.

C. Tree storage. (prevent recursion on identical branches). For each section of result tree store the following, regarding the tree with leaves: (next price paid, # of times bought). (it may be easier to store this in an 2d array, if the prices are sorted, and the corresponding prices' index is the index in the array).

[Avatar19]

hey jkmyoung thanks for the reply, what i mean by the logic of this question is that, the example that i listed in the original post is what they output as a correct answer
Example
Suppose that a stock has had historical prices of R10,
R5, R30, R25, R23, R25, R20, R24 and R22. Then the
maximum number of times it could be bought would be
4, buying it for R30, R25, R24 and R22. Notice that the
price must strictly decrease each time, so it cannot be
bought twice for R25.

what i was asking is if anyone understands how according to them, in the example listed above that the answer they give is correct, i.e. as they say,that this stock could only be bought at R30,R25,R24,R22
Could you pls explain how why this is so??
thanks
Ava19

[jkmyoung]

R30 R25 R23 R20, is just as valid a solution.
Are you asking:
1. How do we know this is a solution which fits the criteria?
b. The numbers actually occur in the data in such an order?
2. How do we know if this is the best solution?

If 1, check each of the numbers. If a number is greater or equal to the number before it, then it is not a valid solution.
b) Then, this solution actually must exist in the data. Eg, find the first R30, then find the next R25, etc. If we can't find the solution in the data, it also is not a valid solution. Eg, R30 R25 R22 R20 is not a valid solution.

If 2, You have to figure out the best possible solution(s) by some algorithm and ensure this is the best one.

[Avatar19]

Thank you for your patience with me,the question just clicked, I understand it now!!
Thanks Ava19

[tyagithehacker]

Thank you for your patience with me,the question just clicked, I understand it now!!
Thanks Ava19

cn u plz explain the logic...??

[jkmyoung]

What logic are you looking for? 1, 1b, 2? (See post 4)