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

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

你最多可以进行 $k$ 笔交易，每笔交易可以是以下任一类型：

• 普通交易：在第 $i$ 天买入，然后在之后的第 $j$ 天卖出，其中 $i < j$。你的利润是 prices[j] - prices[i]
• 做空交易：在第 $i$ 天卖出，然后在之后的第 $j$ 天买回，其中 $i < j$。你的利润是 prices[i] - prices[j]

简单来说：同一笔交易，既可以先买再卖，也可以先卖再买

注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作，也就是说 你不能同时参与多笔交易

你最多可以完成 $k$ 笔交易，请问你的最大利润是多少？

输入格式

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

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

输出格式

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

5 2
1 7 9 8 2

14

9 3
12 16 19 19 8 1 19 13 9

36

提示

【样例 1 解释】

我们可以通过 $2$ 笔交易获得 $14$ 元的利润：

• 一笔普通交易：第 $0$ 天以 $1$ 元买入，第 $2$ 天以 $9$ 元卖出。
• 一笔做空交易：第 $3$ 天以 $8$ 元卖出，第 $4$ 天以 $2$ 元买回

【样例 2 解释】

我们可以通过 $3$ 笔交易获得 $36$ 元的利润：

• 一笔普通交易：第 $0$ 天以 $12$ 元买入，第 $2$ 天以 $19$ 元卖出。
• 一笔做空交易：第 $3$ 天以 $19$ 元卖出，第 $4$ 天以 $8$ 元买回。
• 一笔普通交易：第 $5$ 天以 $1$ 元买入，第 $6$ 天以 $19$ 元卖出

【数据范围】

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

来源

• 参考答案