【普及】买卖股票的最佳时机_4

给定一个数组 $prices$ ，它的第 $i$ 个元素 $prices[i]$ 表示一支给定股票第 $i$ 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 $k$ 笔交易，也就是说，你最多可以买 $k$ 次，卖 $k$ 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含 $2$ 个正整数 $n, k(1 \le n \le 10^5, 1 \le k \le 100)$，表示 $prices[]$ 的长度和交易笔数上限

第二行包含 $n$ 个正整数，表示 $prices[i]$

输出格式

对于每组数据输出一行，包含答案

3 2
2 4 1

2

6 2
3 2 6 5 0 3

7

提示

【样例 1 解释】

• 在第 $1$ 天买入（价格为 $2$），第 $2$ 天卖出（价格为 $4$）
• 获利 $4 - 2 = 2$

【样例 2 解释】

• 在第 $2$ 天买入（价格为 $2$），第 $3$ 天卖出（价格为 $6$）
• 在第 $5$ 天买入（价格为 $0$），第 $6$ 天卖出（价格为 $3$）
• 获利 $(6 - 2) + (3 - 0) = 7$

【数据范围】

• $1 \le n \le 10^5, 1 \le k \le 100$
• $0 \le prices[i] \le 10^4$

来源

• 参考答案