🐰😺📊 兔猫信奥学院的 K 次交易探秘 📊😺🐰

在兔猫信奥学院的计算金融试炼场，加菲老师带着小兔和小猫，面前展现了一条股价曲线 prices，以及一次性可完成 最多 k 笔 “买入→卖出” 魔法交易的契约。师傅吩咐：

“在不能同时持有超过一股的前提下，至多买卖 k 次，设计策略，获取最大的净利润。”

输入格式

第一行：整数 k，表示最多交易次数。
第二行：整数 n，表示天数（股价数组长度）。
第三行：n 个整数 prices[i]，用空格分隔，第 i 天的股价。

• 1 ≤ k ≤ 1000
• 1 ≤ n ≤ 100000
• 0 ≤ prices[i] ≤ 1000

输出格式

输出一个整数，表示在至多 k 笔交易限制下，能够获得的最大净利润。

示例 1

2
3
2 4 1

2

• 解释：
  只需要一次交易：第 0 天买入（价 2），第 1 天卖出（价 4），利润 2。

示例 2

2
6
3 2 6 5 0 3

7

• 解释：
  • 第 1 天（2）买入，第 2 天（6）卖出，利润 4；
  • 第 4 天（0）买入，第 5 天（3）卖出，利润 3；
    总利润 7。

🎓 加菲老师寄语：
掌握「无限次交易优化」与「K 次交易 DP」两种思路，你就能灵活应对各种交易次数限制。祝你算法与投资双丰收！