4069. 买卖股票的最佳时机含冷冻期 II 🔒
难度中等
题目描述
给定一个长度为 n 的整数数组 prices，其中 prices[i] 表示第 i 天的股票价格。
同时给定一个整数 cooldown 和一个长度为 n 的整数数组 costs。其中，costs[k] 表示一笔股票恰好持有 k 天时需要支付的 总持有费用。
你可以进行任意次数的交易，也可以不进行任何交易，但需要满足以下规则：
- 任意时刻你 最多只能持有一股 股票。在再次买入之前，必须先卖出当前持有的股票。
- 如果你在第
j天卖出股票，那么最早可以在第j + cooldown + 1天再次买入股票。 - 如果你在第
i天买入，并在第j天卖出，那么持有时长为j - i天。你需要为该笔交易支付一次费用costs[j - i]。
在第 i 天买入并在第 j 天卖出的利润为 prices[j] - prices[i] - costs[j - i]。
返回你能够获得的 最大总利润。如果不存在任何有利可图的交易，则返回 0。
示例 1：
输入： prices = [1,5,3], cooldown = 1, costs = [2,0,1]
输出： 4
解释：
最优策略如下：
- 在第 0 天以
prices[0] = 1的价格买入。 - 在第 1 天以
prices[1] = 5的价格卖出。持有时长为 1 天，因此持有费用为costs[1] = 0。 - 因此，该笔交易的利润为
5 - 1 - 0 = 4。 - 卖出后，由于
cooldown = 1，第 2 天不能再买入股票，因此无法进行更多交易。 - 能够获得的最大利润为 4。
示例 2：
输入： prices = [1,2,5], cooldown = 0, costs = [0,2,1]
输出： 3
解释：
最优策略如下：
- 在第 0 天以
prices[0] = 1的价格买入。 - 在第 2 天以
prices[2] = 5的价格卖出。持有时长为 2 天，因此持有费用为costs[2] = 1。 - 因此，该笔交易的利润为
5 - 1 - 1 = 3。 - 继续进行交易无法获得更高利润。能够获得的最大利润为 3。
示例 3：
输入： prices = [4,1,7], cooldown = 2, costs = [3,0,1]
输出： 6
解释：
最优策略如下：
- 在第 1 天以
prices[1] = 1的价格买入。 - 在第 2 天以
prices[2] = 7的价格卖出。持有时长为 1 天，因此持有费用为costs[1] = 0。 - 该笔交易的利润为
7 - 1 - 0 = 6。 - 之后无法再进行更多交易。能够获得的最大利润为 6。
示例 4：
输入： prices = [3,1,4], cooldown = 0, costs = [2,1,0]
输出： 2
解释：
最优策略如下：
- 在第 1 天以
prices[1] = 1的价格买入。 - 在第 2 天以
prices[2] = 4的价格卖出。持有时长为 1 天，因此持有费用为costs[1] = 1。 - 因此，该笔交易的利润为
4 - 1 - 1 = 2。 - 继续进行交易无法获得更高利润。能够获得的最大利润为 2。
提示：
1 <= n == prices.length <= 15001 <= prices[i] <= 1050 <= cooldown <= n - 1costs.length == n0 <= costs[i] <= 105
解法
方法一
1 | |
1 | |
1 | |
1 | |