解题思路

• 本题等价于经典问题“最多进行 k 次买卖的最大利润”。

• 若 k >= n/2（天数的一半），约束形同无约束：可以把所有上升幅度相加（贪心：把每个相邻正差累加）。

• 否则使用动态规划的“交易次数 × 持有状态”转移，滚动优化到一维：

  • 定义：

    • buy[j]：完成 j 次卖出后、再买入并持有的最大收益（第 j+1 笔正在持有），

题目内容

你是某著名 $IP$ 毛绒公仔的收藏家，手上有一张该公仔的价目表 $prices$ 。其中 $prices[i]$ 日是第 $i$ 天每箱公仔的价格、共 $n$ 天。

由于公平交易规制、规则如下:

• 你每天最多只能存货 $1$ 箱。

• 最多可以进行 $k$ 笔交易(买入 $k$ 次、卖出 $k$ 次)

目标:在 $n$ 天内任意买卖，求你能赚到的最大差价利润。

样例1

输入

[7,1,5,3,6,4],2

输出

7

说明

在第 $2$ 天(公仔价格 $=1$ )的时候买入，在第 $3$ 天(公仔价格 $=5$ )的时候卖出，这笔交易所能获得利润 $=5-1=4$ 。

随后，在第 $4$ 天(公仔价格 $=3$ )的时候买入，在第 $5$ 天(公仔价格 $=6$ )的时候卖出,这笔交易所能获得利润 $=6-3=3$ 。

样例2

输入

[8,6,5,3,3],2

输出

0

说明

交易一直无法获得正利润，不交易最终利润最大为 $0$