Problem link: http://opc.iarcs.org.in/index.php/problems/BUFFALOES
If the constraint wasn’t there, it can be solved easily i.e. The array of prices can be split (not entirely) into sub arrays of elements in ascending order where Ramu purchases the buffalo at the price of the 1st element of the sub array and sells it at the price of the last element of the sub array.
Considering the example case in the problem below
10 12 8 11 11 10 12 15 13 10
This can be split into sub arrays: [10,12], [8,11,11], [10,12,15]
Ramu buys on day 1, sells on day 2 -->Profit = 2
Ramu buys on day 3, sells on day 4/5 --> Profit = 3
Ramu buys on day 6, sells on day 8 --> Profit = 5
Total profit = 10
But since the constraint IS there, I am really confused. I desperately googled for an idea, and found this:
http://www.cplusplus.com/forum/general/89500/
It was an eye opener. I had never thought of it this way, but only ended up getting it working without the constraint.
This is the flowchart of the algorithm described in the above link which I tried.
https://www.dropbox.com/s/d760hkta7qhkg17/Speculating%20buffaloes.pdf?dl=0
I don’t get how to eliminate the chains with the constraint. How do I go about further (that is with respect to the above algorithm since it looks pretty :P) ?