问题如下:
拉姆是一个懒惰的农民。他继承了他父亲相当大的农场和一座漂亮的房子。拉姆把农田租给别人，赚取相当可观的收入。他的父亲过去曾在家里养一只水牛并出售它的牛奶，但水牛在他父亲去世后几天就死了。
拉姆也想通过养牛赚点钱，但方法与众不同。他决定自己未来的发展在于对牛进行投机。在他的村里，每天都有人买卖水牛。价格随着一年的变化而波动，但在任何一天，价格总是相同的。
他决定在价格低时购买水牛，在价格高时出售水牛，并在此过程中积累巨大财富。不幸的是，他的房子只能容纳一头水牛，因此他最多只能拥有一头水牛。
在进入水牛市场之前，他决定检查最近几天水牛价格的变化情况，并确定他可能获得的最大利润。假设在过去的10天里，一头水牛的价格变化如下:10 12 8 11 11 10 12 15 13 10
拉姆是一个懒人，他估计在过去的10天里他最多愿意参观市场5次（每次买或卖一头水牛）。鉴于此，他可能获得的最大利润为9卢比。要实现这一点，他在第1天购买一头水牛，在第2天出售它，在第3天再买一头，第8天出售。如果他不那么懒惰，愿意参观市场6次，那么他可以赚更多的钱。他可以在第1天买入，第2天卖出，在第3天买入，在第4天卖出，在第6天买入，并在第8天卖出以获得10卢比的利润。
你的任务是帮助拉姆计算他能够在投机水牛上获得的最大收益，给定一个期间内每日水牛价格的历史记录以及拉姆在此期间内最多访问牲畜市场的限制。输入格式
输入的第一行包含两个整数N和K，其中N是可用价格数据的天数，K是拉姆在此期间内最多愿意访问牲畜市场的次数。接下来的N行（第2、3, ..., N+1行）每行包含一个正整数。第i+1行上的整数，1 ≤ i ≤ N，表示第i天一头水牛的价格。输出格式
一个非负整数，表示拉姆在最多访问K次市场的情况下能够获得的最大利润。
您可以假设N≤400，K≤400。
时间限制= 3秒。
如果没有限制k，我们可以使用贪心算法解决这个问题，
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
但是我们不能在这里使用它，因为是否访问特定的一天取决于我们访问了多少天。
以下是我尝试过的：
//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
这是一个在线评测问题，当我提交时，有些测试用例超时，有些错误，只有一个测试用例正确。
我的方法有什么问题？它为什么会慢，因为它需要约O(NK)的时间，其中N和K < 400。如何改进算法以正确解决问题？
编辑：这不是作业，我在这里找到了这个问题：http://opc.iarcs.org.in/index.php/problems/BUFFALOES
