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

Question

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.
You may assume that N ≤ 400 and K ≤ 400.
Time limit = 3sec.

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 out 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 it takes about O(NK) time where N and K < 400.
How can i improve my algorithm to solve the problem correctly?

EDIT: This is not homework, i found this problem here: http://opc.iarcs.org.in/index.php/problems/BUFFALOES

Answer 1

I haven't analyzed it closely, but it seems to me your idea for the lazy farmer is a little too greedy. I am having a hard time visualizing your linked list, or the operations on it.

I think a good way to think about this, without worrying about efficiency, is to cast this into a graph, where each day is a node in the graph.

If we have an industrious trader willing to visit the market as often as possible, it looks like Figure 1 below, where I've taken the first few days of your example. Arcs are drawn from every day to every later day in the graph, and the arcs are weighted as follows:

• Consecutive days must have an arc-- either weighted with the profit of buying and then selling on the next day, or (if such an activity would be a loss) weighted zero
• Non-consecutive days only need an arc if the profit is positive. (Although you could draw in the zero-weight arcs for non-profitable pairs, I have suppressed them below so that the graph is readable.)

This graph takes O(N^2) comparison/subtractions to create. Once you have this graph, finding the best plan for the farmer is equivalent to finding the longest path (e.g., the path from the first day to the last day with the largest sum of arc values) through the graph. Usually, finding the longest path through the graph is NP-Complete, but in this case, we have a directed acyclic graph-- you can simply negate all the edge weights and find the shortest path with Dijkstra's algorithm in polynomial time.

To deal with a lazy farmer, you need to adapt this graph structure in such a way that it "counts" the non-zero arcs. We do this by making the graph bigger. A lot bigger. If the farmer is willing to make k trips to the market, he has floor(k/2) buy/sell pairs. Let's call that number X, and draw the nodes of our graph each X+1 times.

Each consecutive arc in the same row (regardless of profit for that day) has a weight of 0. The arcs of positive length are redirected to the row below. Figure 2 shows what this looks like if the farmer is willing to make 4 trips to the market, for 2 total buy/sell opportunities. You also add a dummy "terminal node" that you can get to from the end of each row, at no cost.

You can see that this "counts" the profit arcs by ensuring that each opportunity to profit moves from row to row, and there is never an opportunity to use the same row more than once. So again, you can find the longest path to find the right answer; and again the graph is directed acyclic so this can be converted to a shortest path problem and solved in polynomial time.

The bad news is, the node and arc count have gone up considerably. Instead of N nodes, you have potentially O(N^2) if k=N. Likewise, instead of O(N^2) arcs, you have O(N^3).

You may be able to do a better in both time and space by casting the problem as a grid, similar to the longest common subsequence problem, but this at least illustrates the structure of the problem.