Algorithm: How do i solve this in a faster and more accurate way?

[meteora]

Here is the question:

Ramu was a lazy farmer. He had inherited a fairly large farm and a nice house from his father. Ramu leased out the farm land to others and earned a rather handsome income. His father used to keep a buffalo at home and sell its milk but the buffalo died a few days after his father did.
Ramu too wanted to make some money from buffaloes, but in a quite a different way. He decided that his future lay in speculating on buffaloes.
In the market in his village, buffaloes were bought and sold everyday. The price fluctuated over the year, but on any single day the price was always the same.
He decided that he would buy buffaloes when the price was low and sell them when the price was high and, in the process, accummulate great wealth. Unfortunately his house had space for just one buffalo and so he could own at most one buffalo at any time.
Before he entered the buffalo market, he decided to examine to examine the variation in the price of buffaloes over the last few days and determine the maximum profit he could have made. Suppose, the price of a buffalo over the last 10 days varied as

10 12 8 11 11 10 12 15 13 10

Ramu is a lazy fellow and he reckoned that he would have been willing to visit the market at most 5 times (each time to either buy or sell a buffalo) over the last 10 days.
Given this, the maximum profit he could have made is 9 rupees. To achieve this, he buys a buffalo on day 1, sells it on day 2, buys one more on day 3 and sells it on day 8.
If he was a little less lazy and was willing to visit the market 6 times, then he could have made more money. He could have bought on day 1, sold on day 2, bought on day 3, sold on day 4, bought on day 6 and sold on day 8 to make a profit of 10 rupees.

Your task is help Ramu calculate the maximum amount he can earn by speculating on buffaloes, given a history of daily buffalo prices over a period and a limit on how many times Ramu is willing to go to the market during this period.

Input format
The first line of the input contains two integers N and K, where N is the number of days for which the price data is available and K is the maximum number of times that Ramu is willing to visit the cattle market.
The next N lines (line 2, 3,...,N+1) contain a single positive integer each. The integer on line i+1, 1 ≤ i ≤ N, indicates the price of a buffalo on day i.

Output format
A single nonnegative integer indicating that maximum amount of profit that Ramu can make if he were to make at most K trips to the market.

Test Data N ≤ 400 and K ≤ 400.
Time Limit 3 secs

If we did not have the constraint k, we could solve this problem using a greedy approach,

while c < N i = c 
         while price[day i] > price[day i+1] increment i
         j = i+1
         while price[day j] < price[day j+1] increment j
         add price[day j] - price[day i] to our profit 
         c = j+1 

But we cant use it here because whether to visit on a particular day or not depends on how many days we visited. Here is what i had tried

 /* Store all the pairs generated in the previous algorithm in a linked
 list L, each element has two attributes buy,sell*/
    while length of L > k/2 
         find an element i in the list such the (L[i].sell- L[i-1].buy) 
          - (L[i-1].buy - L[i-1].sell) - (L[i].buy - L[i].sell) is maximized. 
         Then set L[i-1].sell to L[i].sell and delete i from the list 

This is a problem on an online judge and when i submitted it I got time limit exceeded for some of the test cases and wrong answer for some and correct for just one test case.
What is wrong in my method, and how can it be slow because even if it takes about O(NK) time where N and K < 400.
How can i improve my algorithm to solve the problem correctly?

[Disch]

I love this kind of stuff. Super fun.

This reminds me of an approach I took to a compression algorithm a long time ago. I would approach it like this:

Ignoring the 'K' restriction for now...

At any given day, Ramu has 2 choices:
1) he can do nothing
or
2) he can trade (sell if he has a buffalo, or buy if he doesn't)


With that in mind, you can form several "chains" which represent different paths Ramu could take. To speed up the search, after each day you can go through and eliminate all chains except for 2. You only need to keep tabs on the two chains where Ramu has the most money (one chain with a buffalo, and one without)

It's difficult to put in psuedo-code... so let's walk through the example:

10 12 8 11 11 10 12 15 13 10

After day 1, possible outcomes for Ramu is he could have bought a buffalo (leaving him -10 rupees + buffalo), or he could have done nothing (leaving him with 0 rupees)

So there's 2 chains: 0 and -10* (* denotes Ramu has a buffalo)

After day 2, that turns into 4 chains, because each chain could decide to buy/sell or do nothing

Chains after day 2: 0, 2, -12*, -10*

0 if he did nothing both days
2 if he bought on day 1 and sold on day 2
-12* if he did nothing day 1 and bought on day 2
-10* if he bought on day 1 and did nothing on day 2


But now after seeing these chains, we can eliminate chains 0 and -12* because they are inferior paths to 2 and -10*.

after the final day, you just take the chain with the highest rupee value as the solution.

My big O notation sucks but I think that works out to something like O(4*N)



Reintroducing the 'K' restriction changes it slightly, but not much. All you'd have to do in that case is keep track of how many days Ramu took action. And when eliminating chains, you'd only eliminate a chain if another chain has more money and <= the number of action days.


EDIT:

Is this a public problem? Like could I submit a program to this online judge and see if it works?

[meteora]

thanks a lot for your solution, and you can submit the problem here http://opc.iarcs.org.in/index.php/problems/BUFFALOES but you may have to create an account.

[Disch]

Sweet. Got it on the first try.

http://opc.iarcs.org.in/index.php/results/12723


I don't know why those are so much fun... but they are.


EDIT: Balls... that site isn't using a C++11 compiler. Laaaaaame.

[meteora]

Even i got it accepted, i was stuck on this problem for so long, thanks again