题目描述

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。

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

输入格式

• 第一行包含整数 N 和 k，表示数组的长度以及你可以完成的最大交易笔数
• 第二行包含 N 个不超过 10000 的非负整数，表示完整的数组

输出格式

输出一个整数，表示最大利润

数据范围

• 1 ≤ N ≤ 10⁵
• 1 ≤ k ≤ 100

输入样例1

3 2
2 4 1

输出样例1

2

输入样例2

6 2
3 2 6 5 0 3

输出样例2

7

样例解释

样例1：
在第 1 天（股票价格 = 2）买入，第 2 天（价格 = 4）卖出，利润 = 4-2 = 2

样例2：

1. 第 2 天（价格 = 2）买入，第 3 天（价格 = 6）卖出，利润 = 6-2 = 4
2. 第 5 天（价格 = 0）买入，第 6 天（价格 = 3）卖出，利润 = 3-0 = 3
   总利润 = 4 + 3 = 7

解题提示

1. 需要使用动态规划来解决此问题
2. 考虑状态表示：f[i][j] 表示第 i 天完成 j 笔交易的最大利润
3. 注意交易限制条件（不能同时持有多笔交易）
4. 时间复杂度应优化至 O(N*k) 级别

补充说明：

1. 题目强调交易次数限制和不能同时持有多笔交易的约束条件
2. 数据范围较大（N≤10⁵），需要高效算法
3. 样例解释清晰展示了交易时机的选择和利润计算方式
4. 适合考察动态规划的状态设计和转移优化能力
5. 题目来自LeetCode